idnits 2.17.1 draft-ietf-ospf-manet-mpr-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.i or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? -- It seems you're using the 'non-IETF stream' Licence Notice instead 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 lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (January 17, 2009) is 5575 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Experimental ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 4813 (Obsoleted by RFC 5613) Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Open Shortest Path (OSPF) E. Baccelli 3 Internet-Draft P. Jacquet 4 Intended status: Experimental INRIA 5 Expires: July 21, 2009 D. Nguyen 6 CRC 7 T. Clausen 8 LIX, Ecole Polytechnique, France 9 January 17, 2009 11 OSPF MPR Extension for Ad Hoc Networks 12 draft-ietf-ospf-manet-mpr-04 14 Status of This Memo 16 This Internet-Draft is submitted to IETF in full conformance with the 17 provisions of BCP 78 and BCP 79. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as Internet- 22 Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt. 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html. 35 This Internet-Draft will expire on July 21, 2009. 37 Copyright Notice 39 Copyright (c) 2009 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. 49 Abstract 51 This document specifies an OSPFv3 interface type tailored for mobile 52 ad hoc networks. This interface type is derived from the broadcast 53 interface type, and denoted the "OSPFv3 MANET interface type". 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 58 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 6 60 3.1. MANET Characteristics . . . . . . . . . . . . . . . . . . 6 61 3.2. OSPFv3 MANET Interface Characteristics . . . . . . . . . . 6 62 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 7 63 4.1. Efficient Flooding using MPRs . . . . . . . . . . . . . . 7 64 4.2. MPR Topology Reduction . . . . . . . . . . . . . . . . . . 7 65 4.3. Multicast Transmissions of Protocol Packets . . . . . . . 7 66 4.4. MPR Adjacency Reduction . . . . . . . . . . . . . . . . . 8 67 5. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 8 68 5.1. Data Structures . . . . . . . . . . . . . . . . . . . . . 8 69 5.1.1. N(i): Symmetric 1-hop Neighbor Set . . . . . . . . . . 8 70 5.1.2. N2(i): Symmetric strict 2-hop Neighbor Set . . . . . . 9 71 5.1.3. Flooding-MPR set . . . . . . . . . . . . . . . . . . . 9 72 5.1.4. Flooding-MPR-selector set . . . . . . . . . . . . . . 10 73 5.1.5. Path-MPR set . . . . . . . . . . . . . . . . . . . . . 10 74 5.1.6. Path-MPR-selector set . . . . . . . . . . . . . . . . 11 75 5.1.7. MPR set . . . . . . . . . . . . . . . . . . . . . . . 11 76 5.1.8. MPR-selector set . . . . . . . . . . . . . . . . . . . 11 77 5.2. Hello Protocol . . . . . . . . . . . . . . . . . . . . . . 11 78 5.2.1. Flooding-MPR Selection . . . . . . . . . . . . . . . . 12 79 5.2.2. Flooding-MPR Selection Signaling - FMPR TLV . . . . . 12 80 5.2.3. Neighbor Ordering . . . . . . . . . . . . . . . . . . 12 81 5.2.4. Metric Signaling - METRIC-MPR TLV and PMPR TLV . . . . 13 82 5.2.5. Path-MPR Selection . . . . . . . . . . . . . . . . . . 13 83 5.2.6. Path-MPR Selection Signaling - PMPR TLV . . . . . . . 13 84 5.2.7. Hello Packet Processing . . . . . . . . . . . . . . . 14 85 5.3. Adjacencies . . . . . . . . . . . . . . . . . . . . . . . 14 86 5.3.1. Packets over 2-Way Links . . . . . . . . . . . . . . . 15 87 5.3.2. Adjacency Conservation . . . . . . . . . . . . . . . . 15 88 5.4. Link State Advertisements . . . . . . . . . . . . . . . . 15 89 5.4.1. LSA Flooding . . . . . . . . . . . . . . . . . . . . . 16 90 5.4.2. Link State Acknowledgments . . . . . . . . . . . . . . 17 91 5.5. Hybrid Routers . . . . . . . . . . . . . . . . . . . . . . 18 92 5.6. Synch Routers . . . . . . . . . . . . . . . . . . . . . . 19 93 5.7. Routing Table Computation . . . . . . . . . . . . . . . . 19 94 6. Packet Formats . . . . . . . . . . . . . . . . . . . . . . . . 19 95 6.1. Flooding-MPR TLV . . . . . . . . . . . . . . . . . . . . 20 96 6.2. Metric-MPR TLV . . . . . . . . . . . . . . . . . . . . . . 20 97 6.3. Path-MPR TLV . . . . . . . . . . . . . . . . . . . . . . 22 98 7. Security Considerations . . . . . . . . . . . . . . . . . . . 25 99 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 100 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 27 101 9.1. Normative References . . . . . . . . . . . . . . . . . . . 27 102 9.2. Informative References . . . . . . . . . . . . . . . . . . 27 103 Appendix A. Flooding-MPR Selection Heuristic . . . . . . . . . . 28 104 Appendix B. Path-MPR Selection Heuristic . . . . . . . . . . . . 29 105 Appendix C. Contributors . . . . . . . . . . . . . . . . . . . . 30 106 Appendix D. Acknowledgments . . . . . . . . . . . . . . . . . . . 30 108 1. Introduction 110 This document specifies an extension of OSPFv3 [RFC5340] adapted to 111 MANETs [RFC2501], and based on mechanisms providing: 113 Flooding reduction: only a subset of all routers will be involved in 114 (re)transmissions during a flooding operation. 116 Topology reduction: only a subset of links are advertised, hence 117 both the number and the size of LSAs are decreased. 119 Adjacency reduction: adjacencies are brought up only with a subset 120 of neighbors, for lower database synchronization overhead. 122 These mechanisms are based on multipoint relays (MPR), a technique 123 developed in OLSR [RFC3626]. 125 The extension specified in this document integrates into the OSPF 126 framework by defining the OSPFv3 MANET interface type. While this 127 extension enables OSPFv3 to function efficiently on mobile ad hoc 128 networks, operation of OSPFv3 on other types of interfaces or 129 networks, or in areas without OSPFv3 MANET interfaces, remains 130 unaltered. 132 2. Terminology 134 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 135 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 136 "OPTIONAL" in this document are to be interpreted as described in 137 [RFC2119]. 139 This document uses OSPF terminology as defined in [RFC2328] and 140 [RFC5340], LLS terminology as defined in [RFC4813], and introduces 141 the following terminology to the OSPF nomenclature: 143 OSPFv3 MANET interface - the OSPFv3 interface type for MANETs, as 144 specified in this document. 146 Additionally, the following terms are used in this document: 148 MANET router - a router which has only OSPFv3 MANET interface(s). 150 Wired router - a router which has only OSPFv3 interface of types 151 other than OSPFv3 MANET interfaces. 153 Hybrid router - a router which has OSPFv3 interfaces of several 154 types, including at least one of the OSPFv3 MANET interface type. 156 Neighbor - a router, reachable through an OSPFv3 interface (of any 157 type). 159 MANET neighbor - a neighbor, reachable through an OSPFv3 MANET 160 interface. 162 Symmetric 1-hop neighbor - a neighbor, in a state greater than or 163 equal to 2-Way (through an interface of any type). 165 Symmetric strict 2-hop neighbor - a symmetric 1-hop neighbor of a 166 symmetric 1-hop neighbor, which is not itself a symmetric 1-hop 167 neighbor of this router. 169 Symmetric strict 2-hop neighborhood - the set formed by all the 170 symmetric strict 2-hop neighbors of the considered router. 172 Synch router - a router which brings up adjacencies with all of its 173 MANET neighbors. 175 Flooding-MPR - A router which is selected by its symmetric 1-hop 176 neighbor, router X, to retransmit all broadcast protocol packets 177 that it receives from router X, provided that that broadcast 178 protocol packet is not a duplicate, and that the hop limit field 179 of the protocol packet is greater than one. 181 Path-MPR - A router, which is selected by a symmetric 1-hop 182 neighbor, X, as being on the shortest path from a router in the 183 symmetric strict 2-hop neighborhood of router X and to the router 184 X. 186 Multipoint Relay (MPR) - A router which is selected by its symmetric 187 1-hop neighbor as either Flooding-MPR or as Path-MPR, or as both. 189 Flooding-MPR Selector - A router which has selected its symmetric 190 1-hop neighbor, router X, as one of its Flooding-MPRs is a 191 Flooding-MPR selector of router X. 193 Path-MPR Selector - A router which has selected its symmetric 1-hop 194 neighbor, router X, as one of its Path-MPRs is a Path-MPR selector 195 of router X. 197 MPR Selector - A router which has selected its symmetric 1-hop 198 neighbor, router X, as either one of its Flooding-MPRs or as one 199 of its Path-MPRs or as both is an MPR selector of router X. 201 3. Applicability Statement 203 The OSPFv3 MANET interface type, defined in this specification, 204 allows OSPFv3 to be deployed within an area where parts of that area 205 are a mobile ad hoc network (MANET) with moderate mobility 206 properties. 208 3.1. MANET Characteristics 210 MANETs [RFC2501] are networks in which a dynamic network topology is 211 a frequently expected condition, often due to router mobility and/or 212 to varying quality of wireless links - the latter of which also 213 generally entails bandwidth scarcity and interference issues between 214 neighbors. 216 Moreover, MANETs often exhibit "semi-broadcast" properties, i.e. that 217 a router R that makes a transmission within a MANET can only assume 218 that transmission to be received by a subset of the total number of 219 routers within that MANET. Further, if two routers, R1 and R2, each 220 make a transmission, each of these transmissions is not guaranteed to 221 be received by the same subset of routers within the MANET - and this 222 even if each of R1 and R2 can mutually receive transmissions from 223 each other. 225 These characteristics are incompatible with several OSPFv3 226 mechanisms, including, but not limited to, existing mechanisms for 227 control traffic reduction, such as flooding reduction, topology 228 reduction and adjacency reduction (e.g. Designated Router). 230 3.2. OSPFv3 MANET Interface Characteristics 232 An interface of the OSPFv3 MANET interface type is the point of 233 attachment of an OSPFv3 router to a network which may have MANET 234 characteristics. That is, an interface of the OSPFv3 MANET interface 235 type is able to accommodate the MANET characteristics described in 236 Section 3.1. An OSPFv3 MANET interface type is not prescribing a set 237 of behaviors or expectations that the network is required to have. 238 Rather, it is describing operating conditions under which protocols 239 on an interface towards that network must be able to function (i.e. 240 the protocols are required to be able to operate correctly when faced 241 with the characteristics as described in Section 3.1). As such, the 242 OSPFv3 MANET interface type is a generalization of other OSPFv3 243 interface types; for example a protocol operating correctly over an 244 OSPFv3 MANET interface would also operate correctly over an OSPFv3 245 broadcast interface (whereas the inverse would not necessarily be 246 true). 248 Efficient OSPFv3 operation over MANETs relies on control traffic 249 reduction, and using mechanisms appropriate for semi-broadcast. The 250 OSPFv3 MANET interface type, defined in this document, allows 251 networks with MANET characteristics into the OSPFv3 framework by 252 integrating mechanisms (flooding reduction, topology reduction and 253 adjacency reduction) derived from solutions standardized by the MANET 254 working group. 256 4. Protocol Overview and Functioning 258 The OSPFv3 MANET interface type, defined in this specification, makes 259 use of flooding reduction, topology reduction and adjacency 260 reduction, all based on multipoint relaying (MPR) - a technique 261 derived from [RFC3626], as standardized in the MANET working group. 262 Multicast transmissions of protocol packets are used when possible. 264 4.1. Efficient Flooding using MPRs 266 OSPFv3 MANET interfaces use a flooding reduction mechanism denoted 267 MPR flooding [MPR], whereby only a subset of MANET neighbors (those 268 selected as Flooding-MPR) participate in a flooding operation. This 269 reduces the number of (re)transmissions necessary for a flooding 270 operation [MPR-analysis], while retaining resilience to transmission 271 errors (inherent when using wireless links), and obsolete two-hop 272 neighbor information (e.g. as caused by router mobility) 273 [MPR-robustness]. 275 4.2. MPR Topology Reduction 277 OSPFv3 MANET interfaces use a topology reduction mechanism denoted 278 MPR topology reduction, whereby only necessary links to MANET 279 neighbors (those identified by Path-MPR selection as belonging to 280 shortest paths) are included in LSAs. Routers in a MANET 281 periodically generate and flood Router-LSAs describing their 282 selection of such links to their Path-MPRs. Such links are reported 283 as point-to-point links. This reduces the size of LSAs originated by 284 routers on a MANET [MPR-topology], while retaining classic OSPF 285 properties: optimal paths using synchronized adjacencies (if 286 synchronized paths are preferred over non-synchronized paths of equal 287 cost). 289 4.3. Multicast Transmissions of Protocol Packets 291 OSPFv3 MANET interfaces employ multicast transmissions, when 292 possible, thereby taking advantage of inherent broadcast capabilities 293 of the medium, if present (with wireless interfaces, this can often 294 be the case [RFC2501]). In particular, LSA acknowledgments are sent 295 via multicast over these interfaces, and retransmissions over the 296 same interfaces are considered as implicit acknowledgments. Jitter 297 management, such as delaying packet (re)transmission, can be employed 298 in order to allow several packets to be bundled into a single 299 transmission, which may avoid superfluous retransmissions due to 300 packet collisions [RFC5148]. 302 4.4. MPR Adjacency Reduction 304 Adjacencies over OSPFv3 MANET interfaces are required to be formed 305 only with a subset of the neighbors of that OSPFv3 MANET interface. 306 No Designated Router or Backup Designated Router are elected on an 307 OSPFv3 MANET interface. Rather, adjacencies are brought up over an 308 OSPFv3 MANET interface only with MPRs and MPR Selectors. Only a 309 small subset of routers in the MANET (called Synch routers) are 310 required to bring up adjacencies with all their MANET neighbors. 311 This reduces the amount of control traffic needed for database 312 synchronization, while ensuring that LSAs still describe only 313 synchronized adjacencies. 315 5. Protocol Details 317 This section complements [RFC5340] and specifies the information that 318 must be maintained, processed and transmitted by routers which 319 operate one or more OSPFv3 MANET interfaces. 321 5.1. Data Structures 323 In addition to the values used in [RFC5340], the type field in the 324 interface data structure can take a new value, "MANET". Furthermore, 325 and in addition to the protocol structures defined by [RFC5340], 326 routers which operate one or more MANET interfaces make use of the 327 data structures described below. 329 5.1.1. N(i): Symmetric 1-hop Neighbor Set 331 The Symmetric 1-hop Neighbor set N(i) records router IDs of the set 332 of symmetric 1-hop neighbors of the router on interface i. More 333 precisely, N(i) records tuples of the form: 335 (1_HOP_SYM_id, 1_HOP_SYM_time) 337 where: 339 1_HOP_SYM_id: is the router ID of the symmetric 1-hop neighbor of 340 this router over the interface i. 342 1_HOP_SYM_time: specifies the time at which the tuple expires and 343 MUST be removed from the set. 345 For convenience throughout this document, N will denote the union of 346 all N(i) sets, for all MANET interfaces on the router. 348 5.1.2. N2(i): Symmetric strict 2-hop Neighbor Set 350 The Symmetric strict 2-hop Neighbor set N2(i) records links between 351 routers in N(i) and their symmetric 1-hop neighbors, excluding: 353 (i) the router performing the computation, 355 (ii) all routers in N(i). 357 More precisely, N2(i) records tuples of the form: 359 (2_HOP_SYM_id, 1_HOP_SYM_id, 2_HOP_SYM_time) 361 where: 363 2_HOP_SYM_id: is the router ID of a symmetric strict 2-hop neighbor. 365 1_HOP_SYM_id: is the router ID of the symmetric 1-hop neighbor of 366 this router through which the symmetric strict 2-hop neighbor can 367 be reached. 369 2_HOP_SYM_time: specifies the time at which the tuple expires and 370 MUST be removed from the set. 372 For convenience throughout this document, N2 will denote the union of 373 all N2(i) sets, for all MANET interfaces on the router. 375 5.1.3. Flooding-MPR set 377 The Flooding-MPR set on interface i records router IDs of a subset of 378 the routers listed in N(i), selected such that through this subset, 379 each router listed in N2(i) is reachable in 2 hops by this router. 380 There is one Flooding-MPR set per MANET interface. More precisely, 381 the Flooding-MPR set records tuples of the form: 383 (Flooding_MPR_id, Flooding_MPR_time) 385 where: 387 Flooding_MPR_id: is the router ID of the symmetric 1-hop neighbor of 388 this router, selected as Flooding-MPR. 390 Flooding_MPR_time: specifies the time at which the tuple expires and 391 MUST be removed from the set. 393 Flooding-MPR selection is detailed in Section 5.2.1. 395 5.1.4. Flooding-MPR-selector set 397 The Flooding-MPR-selector set on interface i records router IDs of 398 the set of symmetric 1-hop neighbors of this router on interface i 399 that have selected this router as Flooding-MPR. There is one 400 Flooding-MPR-selector set per MANET interface. More precisely, the 401 Flooding-MPR-selector set records tuples of the form: 403 (Flooding_MPR_SELECTOR_id, Flooding_MPR_SELECTOR_time) 405 where: 407 Flooding_MPR_SELECTOR_id: is the router ID of the symmetric 1-hop 408 neighbor of this router, that has selected this router as 409 Flooding-MPR. 411 Flooding_MPR_SELECTOR_time: specifies the time at which the tuple 412 expires and MUST be removed from the set. 414 Flooding-MPR selection is detailed in Section 5.2.1. 416 5.1.5. Path-MPR set 418 The Path-MPR set records router IDs of routers in N, that provide 419 shortest paths from routers in N2 and to this router. There is one 420 Path-MPR set per router. More precisely, the Path-MPR set records 421 tuples of the form: 423 (Path_MPR_id, Path_MPR_time) 425 where: 427 Path_MPR_id: is the router ID of the symmetric 1-hop neighbor of 428 this router, selected as Path-MPR. 430 Path_MPR_time: specifies the time at which the tuple expires and 431 MUST be removed from the set. 433 Path-MPR selection is detailed in Section 5.2.5. 435 5.1.6. Path-MPR-selector set 437 The Path-MPR-selector set records router IDs of the set of symmetric 438 1-hop neighbors over any MANET interface that have selected this 439 router as Path-MPR. There is one Path-MPR-selector set per router. 440 More precisely, the Path-MPR-selector set records tuples of the form: 442 (Path_MPR_SELECTOR_id, Path_MPR_SELECTOR_time) 444 where: 446 Path_MPR_SELECTOR_id: is the router ID of the symmetric 1-hop 447 neighbor of this router, that has selected this router as Path- 448 MPR. 450 Path_MPR_SELECTOR_time: specifies the time at which the tuple 451 expires and MUST be removed from the set. 453 Path-MPR selection is detailed in Section 5.2.5. 455 5.1.7. MPR set 457 The MPR set is the union of the Flooding-MPR set(s) and the Path-MPR 458 set. There is one MPR set per router. 460 5.1.8. MPR-selector set 462 The MPR-Selector Set is the union of the Flooding-MPR-selector set(s) 463 and the Path-MPR-selector set. There is one MPR-selector set per 464 router. 466 5.2. Hello Protocol 468 On OSPFv3 MANET interfaces, packets are sent, received and processed 469 as defined in [RFC5340] and [RFC2328], augmented for MPR selection as 470 detailed in this section. 472 All additional signaling for OSPFv3 MANET interfaces is done through 473 inclusion of TLVs within an LLS block [RFC4813], appended to Hello 474 packets. If an LLS block is not already present, an LLS block MUST 475 be created and appended to the Hello packets. 477 Hello packets sent over an OSPFv3 MANET interface MUST have the L bit 478 of the OSPF Options field set, as per [RFC4813], indicating the 479 presence of an LLS block. 481 This document defines and employs the following TLVs in Hello packets 482 sent over OSPFv3 MANET interfaces: 484 FMPR - signaling Flooding-MPR selection; 486 PMPR - signaling Path-MPR selection; 488 METRIC-MPR - signaling metrics. 490 The layout and internal structure of these TLVs is detailed in 491 Section 6. 493 5.2.1. Flooding-MPR Selection 495 The objective of Flooding-MPR selection is for a router to select a 496 subset of its neighbors such that a packet, retransmitted by these 497 selected neighbors, will be received by all routers 2 hops away. 498 This property is called the Flooding-MPR "coverage criterion". The 499 Flooding-MPR set of a router is computed such that, for each OSPFv3 500 MANET interface, it satisfies this criterion. The information 501 required to perform this calculation (i.e. link sensing and 502 neighborhood information) is acquired through periodic exchange of 503 OSPFv3 Hello packets. 505 Flooding-MPRs are computed by each router which operates at least one 506 OSPFv3 MANET interface. The smaller the Flooding-MPR set is, the 507 lower the overhead will be. However, while it is not essential that 508 the Flooding-MPR set is minimal, the "coverage criterion" MUST be 509 satisfied by the selected Flooding-MPR set. 511 The willingness of a neighbor router to act as Flooding-MPR MAY be 512 taken into consideration by a heuristic for Flooding-MPR selection. 513 An example heuristic taking willingness into account is given in 514 Appendix A. 516 5.2.2. Flooding-MPR Selection Signaling - FMPR TLV 518 A router MUST signal its Flooding-MPRs set to its neighbors, through 519 including an FMPR TLV in generated Hello packets. Inclusion of this 520 FMPR TLV signals the list of symmetric 1-hop neighbors that the 521 sending router has selected as Flooding-MPR, as well as the 522 willingness of the sending router to be elected Flooding-MPR by other 523 routers. The FMPR TLV structure is detailed in Section 6.1. 525 5.2.3. Neighbor Ordering 527 Neighbors listed in the Hello packets sent over OSPFv3 MANET 528 interfaces MUST be included in the order as given below: 530 1. symmetric 1-hop neighbors which are selected as Flooding-MPRs; 531 2. other symmetric 1-hop neighbors; 533 3. other 1-hop neighbors. 535 This ordering allows correct interpretation of an included FMPR TLV. 537 5.2.4. Metric Signaling - METRIC-MPR TLV and PMPR TLV 539 Hello packets sent over OSPFv3 MANET interfaces MUST advertise the 540 costs of links towards ALL the symmetric MANET neighbors of the 541 sending router. If the sending router has more than one OSPFv3 MANET 542 interfaces, links to ALL the symmetric MANET neighbors over ALL the 543 OSPFv3 MANET interfaces of that router MUST have their costs 544 advertised. 546 The costs of the links between the router and each of its MANET 547 neighbors on the OSPFv3 MANET interface over which the Hello packet 548 is sent MUST be signaled through including METRIC-MPR TLVs. The 549 METRIC-MPR TLV structure is detailed in Section 6.2. 551 Moreover, the lowest cost from each MANET neighbor towards the router 552 (regardless of over which interface) MUST be specified in the 553 included PMPR TLV. Note that the lowest cost can be over an 554 interface which is not an OSPFv3 MANET interface. 556 5.2.5. Path-MPR Selection 558 A router which has one or more OSPFv3 MANET interface(s) MUST select 559 a Path-MPR set from among routers in N. Routers in the Path-MPR set 560 of a router are those which take part in the shortest (with respect 561 to the metrics used) path from routers in N2 and to this router. A 562 heuristic for Path-MPR selection is given in Appendix B. 564 5.2.6. Path-MPR Selection Signaling - PMPR TLV 566 A router MUST signal its Path-MPR set to its neighbors, through 567 including a PMPR TLV in generated Hello packets. 569 A PMPR TLV MUST contain a list of IDs of all symmetric 1-hop 570 neighbors of all OSPFv3 MANET interfaces of the router. These IDs 571 MUST be included in the PMPR TLV in the order as given below: 573 1. Neighbors which are both adjacent AND are selected as Path-MPR 574 for any OSPFv3 MANET interface of the router generating the Hello 575 packet. 577 2. Neighbors which are adjacent over any OSPFv3 MANET interface of 578 the router generating the Hello packet. 580 3. Symmetric 1-hop neighbors on any OSPFv3 MANET interface of the 581 router generating the Hello packet, which have not been 582 previously included in this PMPR TLV. 584 The list of neighbor IDs is followed by a list of costs for the links 585 from these neighbors and to the router generating the Hello packet 586 containing this PMPR TLV, as detailed in Section 5.2.4. The PMPR TLV 587 structure is detailed in Section 6.3. 589 5.2.7. Hello Packet Processing 591 In addition to the processing specified in [RFC5340], N and N2 MUST 592 be updated when received Hello packets indicate changes to the 593 neighborhood of an OSPFv3 MANET interface i. In particular, if a 594 received Hello packet signals that a tuple in N (or N2) is to be 595 deleted, the deletion is done immediately, without waiting for the 596 tuple to expire. Note that N2 records not only 2-hop neighbors 597 listed in received Hellos, but also 2-hop neighbors listed in the 598 appended PMPR TLVs. 600 The Flooding-MPR set MUST be recomputed when either of N(i) or N2(i) 601 has changed. The Path-MPR set MUST be recomputed when either of N or 602 N2 has changed. Moreover, the Path-MPR set MUST be recomputed if 603 appended LLS information signals change with respect to one or more 604 link cost(s). 606 The Flooding-MPR selector set and the Path-MPR selector set MUST be 607 updated upon receipt of a Hello packet containing LLS information 608 indicating changes in the list of neighbors that has selected the 609 router as MPR. 611 If a Hello with the S bit set is received on a OSPFv3 MANET interface 612 of a router, from a non-adjacent neighbor, the router MUST transition 613 this neighbor's state to ExStart. 615 5.3. Adjacencies 617 Adjacencies are brought up between OSPFv3 MANET interfaces as 618 described in [RFC5340] and [RFC2328]. However, in order to reduce 619 the control traffic overhead over the OSPFv3 MANET interfaces, a 620 router which has one or more such OSPFv3 MANET interface(s) MAY bring 621 up adjacencies with only subset of its MANET neighbors. 623 Over an OSPFv3 MANET interface, a router MUST bring up adjacencies 624 with all MANET neighbors which are included in its MPR set and its 625 MPR Selector set; this ensures that beyond the first hop, routes use 626 synchronized links (if synchronized paths are preferred over non- 627 synchronized paths of equal cost). A router MAY bring up adjacencies 628 with other MANET neighbors, at the expense of additional 629 synchronization overhead. 631 5.3.1. Packets over 2-Way Links 633 When a router does not form a full adjacency with a MANET neighbor, 634 the state of that neighbor does not progress beyond 2-Way (as defined 635 in [RFC2328]). A router can send protocol packets, such as LSAs, to 636 a MANET neighbor in 2-Way state. Therefore, any packet received from 637 a symmetric MANET neighbor MUST be processed. 639 As with the OSPF broadcast interface [RFC2328], the next hop in the 640 forwarding table MAY be a neighbor that is not adjacent. However, 641 when a data packet has travelled beyond its first hop, the MPR 642 selection process guarantees that subsequent hops in the SPT will be 643 over adjacencies (if synchronized paths are preferred over non- 644 synchronized paths of equal cost). 646 5.3.2. Adjacency Conservation 648 Adjacencies are torn down according to [RFC2328]. When the MPR set 649 or MPR selector set is updated (due to changes in the neighborhood), 650 and when a neighbor was formerly, but is no longer, in the MPR set or 651 the MPR selector set, then the adjacency with that neighbor is kept, 652 unless the change causes the neighbor to cease being a symmetric 653 1-hop neighbor. 655 When a router receives Hello packets from a symmetric 1-hop neighbor 656 which ceases to list this router as being adjacent (see 657 Section 5.2.6), the state of that neighbor MUST be changed to (i) 658 2-Way if the neighbor is not in the MPR set or the MPR selector set, 659 or (ii) ExStart if the neighbor is in the MPR set or the MPR selector 660 set, or if the neighbor or the router itself is a Synch router. 662 5.4. Link State Advertisements 664 Routers generate Router-LSAs periodically, using the format specified 665 in [RFC5340] and [RFC2328]. 667 Routers which have one or more OSPFv3 MANET interface(s) MUST include 668 the following links in the Router-LSAs that they generate: 670 o links to all neighbors that are in the Path-MPR set; AND 672 o links to all neighbors that are in the Path-MPR Selector set. 674 Routers which have one or more OSPFv3 MANET interface(s) MAY list 675 other links they have through those OSPFv3 MANET interfaces, at the 676 expense of larger LSAs. 678 In addition, routers which have one or more OSPFv3 MANET interface(s) 679 MUST generate updated Router-LSAs when either of the following 680 occurs: 682 o a new adjacency has been brought up, reflecting a change in the 683 MPR set; 685 o a new adjacency has been brought up, reflecting a change in the 686 MPR Selector set; 688 o a formerly adjacent and advertised neighbor ceases to be adjacent; 690 o the cost of a link to (or from) an advertised neighbor has 691 changed. 693 5.4.1. LSA Flooding 695 An originated LSA is flooded according to [RFC5340], out all 696 interfaces concerned by the scope of this LSA. 698 Link State Updates received on an interface of a type other than 699 OSPFv3 MANET interface are processed and flooded according to 700 [RFC2328] and [RFC5340], over every interface. If a Link State 701 Update was received on an OSPFv3 MANET interface, it is processed as 702 follows: 704 1. Consistency checks are performed on the received packet according 705 to [RFC2328] and [RFC5340], and the Link State Update packet is 706 thus associated with a particular neighbor and a particular area. 708 2. If the Link State Update was received from a router other than a 709 symmetric 1-hop neighbor, the Link State Update MUST be discarded 710 without further processing. 712 3. Otherwise, for each LSA contained in Link State Updates received 713 over an OSPFv3 MANET interface, the following steps replace steps 714 1 to 5 of section 13.3 of [RFC2328]. 716 1. If an LSA exists in the Link State Database, with the same 717 Link State ID, LS Type and Advertising Router values as the 718 received LSA, and if the received LSA is not newer (see 719 section 13.1 of [RFC2328]), then the received LSA MUST NOT be 720 processed, except for acknowledgment as described in 721 Section 5.4.2. 723 2. Otherwise, the LSA MUST be attributed a scope according to 724 its type, as specified in section 3.5 of [RFC5340]. 726 3. If the scope of the LSA is link local or reserved, the LSA 727 MUST NOT be flooded on any interface. 729 4. Otherwise: 731 + If the scope of the LSA is the area, the LSA MUST be 732 flooded on all the OSPFv3 interfaces of the router in that 733 area according to the default flooding algorithm described 734 in Section 5.4.1.1. 736 + Otherwise, the LSA MUST be flooded on all the OSPFv3 737 interfaces of the router according to the default flooding 738 algorithm described in Section 5.4.1.1. 740 5.4.1.1. Default LSA Flooding Algorithm 742 The default LSA flooding algorithm is as follows: 744 1. The LSA MUST be installed in the Link State Database. 746 2. The Age of the LSA MUST be increased by InfTransDelay. 748 3. The LSA MUST be retransmitted over all OSPFv3 interfaces of types 749 other than OSPFv3 MANET interface. 751 4. If the sending OSPFv3 interface is a Flooding-MPR selector of 752 this router, then the LSA MUST also be retransmitted over all 753 OSPFv3 MANET interfaces concerned by the scope, with the 754 multicast address all_SPF_Routers. 756 Note that MinLSArrival SHOULD be set to a value that is appropriate 757 to dynamic topologies: LSA updating may need to be more frequent in 758 MANET parts of an OSPF network than in other parts of an OSPF 759 network. 761 5.4.2. Link State Acknowledgments 763 When a router receives an LSA over an OSPFv3 MANET interface, the 764 router MUST proceed to acknowledge the LSA as follows: 766 1. If the LSA was not received from an adjacent neighbor, the router 767 MUST NOT acknowledge it. 769 2. Otherwise, if the LSA was received from an adjacent neighbor and 770 if the LSA is already in the Link State Database (i.e. the LSA 771 has already been received and processed), then the router MUST 772 send an acknowledgment for this LSA on all OSPFv3 MANET 773 interfaces, to the multicast address all_SPF_Routers. 775 3. Otherwise, if the LSA is not already in the Link State Database: 777 1. If the router decides to retransmit the LSA (as part of the 778 flooding procedure), the router MUST NOT acknowledge it, as 779 this retransmission will be considered as an implicit 780 acknowledgment. 782 2. Otherwise, if the router decides to not retransmit the LSA 783 (as part of the flooding procedure), the router MUST send an 784 explicit acknowledgment for this LSA on all OSPFv3 MANET 785 interfaces, to the multicast address all_SPF_Routers. 787 If a router sends an LSA on an OSPFv3 MANET interface, it expects 788 acknowledgments (explicit or implicit) from all adjacent neighbors. 789 In the case where the router did not generate, but simply relays, the 790 LSA, then the router MUST expect acknowledgments (explicit or 791 implicit) only from adjacent neighbors that have not previously 792 acknowledged this LSA. If a router detects that some adjacent 793 neighbor has not acknowledged the LSA, then that router MUST 794 retransmit the LSA. 796 If, due to the MPR flooding reduction mechanism employed for LSA 797 Flooding as described in Section 5.4.1, a router decides to not relay 798 an LSA, the router MUST still expect acknowledgments of this LSA 799 (explicit or implicit) from adjacent neighbors that have not 800 previously acknowledged this LSA. If a router detects that some 801 adjacent neighbor has not acknowledged the LSA, then the router MUST 802 retransmit the LSA. 804 Note that it may be beneficial to aggregate several acknowledgments 805 in the same transmission, taking advantage of native multicasting (if 806 available). A timer wait MAY thus be used before any acknowledgment 807 transmission. 809 Additionally, jitter [RFC5148] on packet (re)transmission MAY be used 810 in order to increase the opportunities to bundle several packets 811 together in each transmission. 813 5.5. Hybrid Routers 815 In addition to the operations described in Section 5.2, Section 5.3 816 and Section 5.4, hybrid routers MUST: 818 o select ALL their MANET neighbors as Path-MPRs. 820 o list adjacencies over OSPFv3 interfaces of types other than OSPFv3 821 MANET interface, as specified in [RFC5340] and [RFC2328], in 822 generated Router-LSAs. 824 5.6. Synch Routers 826 In a network with no hybrid routers, at least one Synch router MUST 827 be selected. A Synch router MUST: 829 o set the S bit in the PMPR TLV appended to the Hello packets it 830 generates; AND 832 o become adjacent with ALL MANET neighbors. 834 A proposed heuristic for selection of Sync routers is as follows: 836 o A router which has a MANET interface and an ID that is higher than 837 the ID of all of its current neighbors, and whose ID is higher 838 than any other ID present in Router-LSAs currently in its Link 839 State Database selects itself as Synch router. 841 Other heuristics are possible, however any heuristic for selecting 842 Synch routers MUST ensure the presence of at least one sync or hybrid 843 router in the network. 845 5.7. Routing Table Computation 847 When routing table (re)computation occurs, in addition to the 848 processing of the Link State Database defined in [RFC5340] and 849 [RFC2328], routers which have one or more MANET interfaces MUST take 850 into account links between themselves and MANET neighbors that are in 851 state 2-Way or higher (as data and protocol packets may be sent, 852 received and processed over these links too). Thus, the connectivity 853 matrix used to compute routes MUST reflect links between the root and 854 all its neighbors in state 2-Way and higher, as well as links 855 described in the Link State Database. 857 6. Packet Formats 859 OSPFv3 packets are as defined by [RFC5340] and [RFC2328]. Additional 860 LLS signaling [RFC4813] is used in Hello packets sent over OSPFv3 861 MANET interfaces, as detailed in this section. 863 This specification uses network byte order (most significant octet 864 first) for all fields. 866 6.1. Flooding-MPR TLV 868 A TLV of Type FMPR is defined for signaling Flooding-MPR selection, 869 shown in Figure 1. 871 0 1 2 3 872 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 873 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 874 | Type=FMPR | Length | 875 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 876 | Willingness | # Sym. Neigh. | # Flood MPR | Reserved | 877 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 879 Figure 1: Flooding-MPR TLV (FMPR) 881 where: 883 Willingness - is an 8 bit unsigned integer field which specifies the 884 willingness of the router to flood link state information on 885 behalf of other routers. It can be set to any integer value from 886 1 to 6. By default, a router SHOULD advertise a willingness of 887 WILL_DEFAULT = 3. 889 # Sym. Neigh. - is an 8 bit unsigned integer field which specifies 890 the number of symmetric 1-hop neighbors. These symmetric 1-hop 891 neighbors are listed first among the neighbors in a Hello packet. 893 # Flood MPR - is an 8 bit unsigned integer field which specifies the 894 number of neighbors selected as Flooding-MPR. These Flooding-MPRs 895 are listed first among the symmetric 1-hop neighbors. 897 Reserved - is an 8 bit field which SHOULD be cleared ('0') on 898 transmission and SHOULD be ignored on reception. 900 6.2. Metric-MPR TLV 902 A TLV of Type METRIC-MPR is defined for signaling costs of links to 903 neighbors, shown in Figure 2. 905 0 1 2 3 906 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 907 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 908 | Type=METRIC-MPR | Length | 909 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 910 | Reserved |U|R| Cost 0 | 911 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 912 | Cost 1 | Cost 2 | 913 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 914 : : 915 : : 916 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 917 | Cost n | Padding | 918 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 920 Figure 2: Metric TLV (METRIC-MPR). 922 where: 924 Reserved - is a 14 bit field which SHOULD be cleared ('0') on 925 transmission and SHOULD be ignored on reception. 927 R - is a binary flag, cleared ('0') if the costs advertised in the 928 TLV are direct (i.e. the costs of the links from the router to the 929 neighbors), set ('1') if the costs advertised are reverse (i.e. 930 the costs of the links from the neighbors to the router). 932 U - is a binary flag, cleared ('0') if each the cost for each link 933 from the sending router and to each advertised neighbor is 934 explicitly included (shown in Figure 3), set ('1') if a single 935 metric value is included which applies to all links (shown in 936 Figure 4). 938 Cost n - is an 8 bit unsigned integer field which specifies the cost 939 of the link, in the direction specified by the R flag, between 940 this router and the neighbor listed at the n-th position in the 941 Hello packet, when counting from the beginning of the Hello packet 942 and with the first neighbor being at position 0. 944 Padding - is a 16 bit field which SHOULD be cleared ('0') on 945 transmission and SHOULD be ignored on reception. Padding is 946 included in order that the TLV is 32bit aligned. Padding MUST be 947 included when the TLV contains an even number of Cost fields, and 948 MUST NOT be included otherwise. 950 0 1 2 3 951 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 952 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 953 | Type=METRIC-MPR | Length | 954 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 955 | Reserved |0|R| Cost 0 | 956 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 957 | Cost 1 | Cost 2 | 958 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 960 Figure 3: Metric Advertisement TLV (METRIC-MPR) example with 961 explicit individual link costs (U=0) and an odd number of Costs (and, 962 hence, no padding). 964 0 1 2 3 965 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 966 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 967 | Type=METRIC-MPR | Length | 968 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 969 | Reserved |1|R| Cost | 970 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 972 Figure 4: Metric Advertisement TLV (METRIC-MPR) example with a 973 single and uniform link cost (U=1) (and, hence, no padding). 975 6.3. Path-MPR TLV 977 A TLV of Type PMPR is defined for signaling Path-MPR selection, shown 978 in Figure 1, as well as the link cost associated with these Path- 979 MPRs. 981 0 1 2 3 982 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 983 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 984 | Type=PMPR | Length | 985 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 986 | # Sym Neigh | # Adj. Neigh | # Path-MPR | Reserved |U|S| 987 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 988 | Neighbor ID | 989 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 990 | Neighbor ID | 991 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 992 : : 993 : : 994 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 995 | Cost 0 | Cost 1 | 996 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 997 : : 998 : : 999 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1000 | Cost n | Padding | 1001 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1003 Figure 5: Path-MPR TLV (PMPR) 1005 # Sym Neigh. - is an 8 bit unsigned integer field which specifies 1006 the number of symmetric 1-hop MANET neighbors of all OSPFv3 MANET 1007 interfaces of the router, listed in the PMPR TLV. 1009 # Adj. Neigh. - is an 8 bit unsigned integer field which specifies 1010 the number of adjacent neighbors. These adjacent neighbors are 1011 listed first among the symmetric 1-hop MANET neighbors of all 1012 OSPFv3 MANET interface of the router in the PMPR TLV. 1014 # Path-MPR - is an 8 bit unsigned integer field which specifies the 1015 number of MANET neighbors selected as Path-MPR. These Path-MPRs 1016 are listed first among the adjacent MANET neighbors in the PMPR 1017 TLV. 1019 Reserved - is a 6 bit field which SHOULD be cleared ('0') on 1020 transmission and SHOULD be ignored on reception. 1022 S - is a binary flag, cleared ('0') if the router brings up 1023 adjacencies only with neighbors in its MPR set and MPR selector 1024 set as per Section 5.3, set ('1') if the router brings up 1025 adjacencies with all MANET neighbors as a Synch router -- as per 1026 Section 5.6. 1028 U - is a binary flag, cleared ('0') if the cost for each link from 1029 each advertised neighbor in the PMPR TLV and to the sending router 1030 is explicitly included (as shown in Figure 6), set ('1') if a 1031 single metric value is included which applies to all links (as 1032 shown in Figure 7). 1034 Neighbor ID - is a 32 bit field which specifies the router ID of a 1035 symmetric 1-hop neighbor of an OSPFv3 MANET interface of the 1036 router. 1038 Cost n - is a 16 bit unsigned integer field which specifies the cost 1039 of the link in the direction from the nth listed advertised 1040 neighbor in the PMPR TLV and towards this router. A default value 1041 of 0xFFFF (i.e. infinity) MUST be advertised, unless information 1042 received via Hello packets from the neighbor specifies otherwise, 1043 in which case the received information MUST be advertised. If a 1044 neighbor is reachable via more than one interface, the cost 1045 advertised MUST be the minimum of the costs by which that neighbor 1046 can be reached. 1048 Padding - is a 16 bit field which SHOULD be cleared ('0') on 1049 transmission and SHOULD be ignored on reception. Padding is 1050 included in order that the PMPR TLV is 32bit aligned. Padding 1051 MUST be included when the TLV contains an odd number of Cost 1052 fields, and MUST NOT be included otherwise. 1054 0 1 2 3 1055 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 1056 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1057 | Type=PMPR | Length | 1058 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1059 | # Adj. Neigh | # Path-MPR | Reserved |0|S| 1060 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1061 | Neighbor ID | 1062 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1063 | Neighbor ID | 1064 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1065 : : 1066 : : 1067 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1068 | Cost 1 | Cost 2 | 1069 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1070 : ....... : 1071 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1072 | Cost n-1 | Cost n | 1073 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1075 Figure 6: Path-MPR TLV (PMPR) with explicit individual link costs 1076 (U=0) and an even number of Cost fields (hence, no padding). 1078 0 1 2 3 1079 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 1080 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1081 | Type=PMPR | Length | 1082 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1083 | # Adj. Neigh | # Path-MPR | Reserved |1|S| 1084 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1085 | Neighbor ID | 1086 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1087 | Neighbor ID | 1088 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1089 | Cost | Padding | 1090 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1092 Figure 7: Path-MPR TLV (PMPR) with a single and uniform link cost 1093 (U=1) (hence, padding included). 1095 7. Security Considerations 1097 [RFC4593] describes generic threats to routing protocols, whose 1098 applicability to OSPFv3 [RFC5340] is not altered by the presence of 1099 OSPFv3 MANET interfaces. As such, the OSPFv3 MANET interface type 1100 does not introduce new security threats to [RFC5340]. 1102 However, the use of a wireless medium and the lack of infrastructure, 1103 as enabled by the use of the OSPFv3 MANET interface type, may render 1104 some of the attacks described in [RFC4593] easier to undertake. 1106 For example, control traffic sniffing and control traffic analysis 1107 are simpler tasks with wireless than with wires, as it is sufficient 1108 to be somewhere within radio range in order to "listen" to wireless 1109 traffic. Inconspicuous wiretapping of the right cable(s) is not 1110 necessary. 1112 In a similar fashion, physical signal interference is also a simpler 1113 task with wireless than with wires, as it is sufficient to emit from 1114 somewhere within radio range in order to be able to disrupt the 1115 communication medium. No complex wire connection is required. 1117 Other types of interference (including not forwarding packets), 1118 spoofing, and different types of falsification or overloading (as 1119 described in [RFC4593]) are also threats to which routers using 1120 OSPFv3 MANET interfaces may be subject. In these cases, the lack of 1121 pre-determined infrastructure or authority, enabled by the use of 1122 OSPFv3 MANET interfaces, may facilitate such attacks by making it 1123 easier to forge legitimacy. 1125 Moreover, the consequence zone of a given threat, and its consequence 1126 period (as defined in [RFC4593]), may also be slightly altered over 1127 the wireless medium, compared to the same threat over wired networks. 1128 Indeed, mobility and the fact that radio range spans "further" than a 1129 mere cable may expand the consequence zone in some cases, while the 1130 more dynamic nature of MANET topologies may decrease the consequence 1131 period, as harmful information (or lack of information) will tend to 1132 be replaced quicker by legitimate information. 1134 8. IANA Considerations 1136 This document defines three LLS TLVs, for which allocation of type 1137 values are requested from the LLS TLV type registry defined in 1138 [RFC4813]. 1140 +------------+------------+--------------+ 1141 | Mnemonic | Type Value | Name | 1142 +------------+------------+--------------+ 1143 | FMPR | tbd | Flooding-MPR | 1144 | METRIC-MPR | tbd | Metric-MPR | 1145 | PMPR | tbd | Path-MPR | 1146 +------------+------------+--------------+ 1148 Table 1: LLS TLV Type Assignments 1150 9. References 1152 9.1. Normative References 1154 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1155 Requirement Levels", RFC 2119, BCP 14, March 1997. 1157 [RFC2328] Moy, J., "OSPF version 2", RFC 2328, 1998. 1159 [RFC5340] Moy, J., Coltun, R., Ferguson, D., and A. Lindem, 1160 "OSPF for IPv6", RFC 5340, 2008. 1162 [RFC4813] Zinin, A., Friedman, B., Roy, A., Nguyen, L., and 1163 D. Yeung, "OSPF Link Local Signaling", RFC 4813, 1164 2007. 1166 9.2. Informative References 1168 [RFC2501] Macker, J. and S. Corson, "MANET Routing Protocol 1169 Performance Issues and Evaluation Considerations", 1170 RFC 2501, January 1999. 1172 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link 1173 State Routing Protocol", RFC 3626, October 2003. 1175 [RFC5148] Adamson, B., Dearlove, C., and T. Clausen, "Jitter 1176 Considerations in MANETs", RFC 5148, 2008. 1178 [MPR] Qayyum, A., Viennot, L., and A. Laouiti,, 1179 "Multipoint Relaying for Flooding Broadcast 1180 Messages in Mobile Wireless Networks", Proceedings 1181 of HICSS , 2002. 1183 [MPR-robustness] Adjih, C., Baccelli, E., Clausen, T., and P. 1184 Jacquet, "On the Robustness and Stability of 1185 Connected Dominated Sets", INRIA Research 1186 Report RR-5609, 2005. 1188 [MPR-analysis] Ngyuen, D. and P. Minet, "Analysis of MPR Selection 1189 in the OLSR Protocol", 2nd Int. Workshop on 1190 Performance Analysis and Enhancement of Wireless 1191 Networks , 2007. 1193 [MPR-topology] Baccelli, E., Clausen, T., and P. Jacquet, "Partial 1194 Topology in an MPR-based Solution for Wireless OSPF 1195 on Mobile Ad Hoc Networks", INRIA Research 1196 Report RR-5619, 2005. 1198 [RFC4593] Barbir, A., Murphy, S., and Y. Yang, "Generic 1199 Threats to Routing Protocols", RFC 4593, 2006. 1201 Appendix A. Flooding-MPR Selection Heuristic 1203 The following specifies a proposed heuristic for selection of 1204 Flooding-MPRs on interface i. It constructs a Flooding-MPR set that 1205 enables a router to reach routers in the 2-hop neighborhood through 1206 relaying by one Flooding-MPR router. 1208 The following terminology will be used in describing the heuristics: 1209 D(Y) is the degree of a 1-hop neighbor, router Y (where Y is a member 1210 of N(i), defined as the number of neighbors of router Y, EXCLUDING 1211 all the members of N(i) and EXCLUDING the router performing the 1212 computation. The proposed heuristic can then be described as 1213 follows. Begin with an empty Flooding-MPR set. Then: 1215 1. Calculate D(Y), where Y is a member of N(i), for all routers in 1216 N(i). 1218 2. Add to the Flooding-MPR set those routers in N(i), which are the 1219 only routers to provide reachability to a router in N2(i). For 1220 example, if router B in N2(i) can be reached only through a 1221 router A in N(i), then add router A to the Flooding-MPR set. 1222 Remove the routers from N2(i) which are now covered by a router 1223 in the Flooding-MPR set. 1225 3. While there exist routers in N2(i) which are not covered by at 1226 least one router in the Flooding-MPR set: 1228 1. For each router in N(i), calculate the reachability, i.e. the 1229 number of routers in N2(i) which are not yet covered by at 1230 least one router in the Flooding-MPR set, and which are 1231 reachable through this 1-hop neighbor; 1233 2. Select as a Flooding-MPR the neighbor with highest 1234 willingness among the routers in N(i) with non-zero 1235 reachability. In case of a tie among routers with same 1236 willingness, select the router which provides reachability to 1237 the maximum number of routers in N2(i). In case of another 1238 tie between routers also providing the same amount of 1239 reachability, select as Flooding-MPR the router whose D(Y) is 1240 greater. Remove the routers from N2(i) which are now covered 1241 by a router in the Flooding-MPR set. 1243 4. As an optimization, consider in increasing order of willingness 1244 each router Y in the Flooding-MPR set: if all routers in N2(i) 1245 are still covered by at least one router in the Flooding-MPR set 1246 when excluding router Y, then router Y MAY be removed from the 1247 Flooding-MPR set. 1249 Other algorithms, as well as improvements over this algorithm, are 1250 possible. Different routers may use different algorithms 1251 independently. However, the algorithm used MUST provide the router 1252 with a Flooding-MPR set that fulfills the flooding coverage 1253 criterion, i.e. it MUST select a Flooding-MPR set such that any 2-hop 1254 neighbor is covered by at least one Flooding-MPR router. 1256 Appendix B. Path-MPR Selection Heuristic 1258 The following specifies a proposed heuristic for calculating a Path- 1259 MPR set that enables a router to reach routers in the 2-hop 1260 neighborhood through shortest paths via routers in its Path-MPR set. 1261 The following terminology will be used for describing this heuristic: 1263 A - The router performing the Path-MPR set calculation. 1265 B, C, D, .... - Other routers in the network. 1267 cost(A, B) - The cost of the path through the direct link, from A to 1268 B. 1270 dist(C, A) - The cost of the shortest path from C to A. 1272 A cost matrix is populated with the values of the costs of links 1273 originating from router A (available locally) and by values listed in 1274 Hello packets received from neighbor routers. More precisely, the 1275 cost matrix is populated as follows: 1277 1. The coefficients of the cost matrix are set by default to 0xFFFF 1278 (maximal value, i.e. infinity). 1280 2. The coefficient cost(A,B) of the cost matrix for a link from 1281 router A to a neighbor B (the direct cost for this link) is set 1282 to the minimum cost over all interfaces that feature router B as 1283 a symmetric 1-hop neighbor. The reverse cost for this link, 1284 cost(B,A), is set at the value received in Hello packets from 1285 router B. If router B is reachable through several interfaces at 1286 the same time, cost(B,A) is set as the minimum cost advertised by 1287 router B for its links towards router A. 1289 3. The coefficients of the cost matrix concerning the link between 1290 two neighbors of A, routers C and B, are populated at the 1291 reception of their Hello packets. The cost (B,C) is set to the 1292 value advertised by the Hello packets from B, and respectively, 1293 the cost (C,B) is set to the value advertised in Hello packets 1294 from C. 1296 4. The coefficients of the cost matrix, cost(B,C) for a link that 1297 connects a neighbor B to a 2-hop neighbor C is obtained via the 1298 Hello packets received from router B. In this case cost(B,C) and 1299 cost(C,B) are respectively set to the values advertised by router 1300 B for the direct cost and reverse cost for node C. 1302 Once the cost matrix is populated, the proposed heuristic can then be 1303 described as follows. Begin with an empty Path-MPR set. Then: 1305 1. Using the cost matrix and the Dijkstra algorithm, compute the 1306 router distance vector, i.e. the shortest distance for each pair 1307 (X,A) where X is in N or N2 minimizing the sum of the cost of the 1308 path between X and A. 1310 2. Compute N' as the subset of N made of the elements X such that 1311 cost(X,A)=dist(X,A). 1313 3. Compute N2' as the subset of N and N2 made of the elements Y that 1314 do not belong to N' and such that there exist X in N' such 1315 cost(Y,X)+cost(X,A)=dist(Y,A). 1317 4. Compute the MPR selection algorithm presented in Appendix A with 1318 N' instead of N(i) and N2' instead of N2(i). The resulting MPR 1319 set is the Path-MPR set. 1321 Other algorithms, as well as improvements over this algorithm, are 1322 possible. Different routers may use different algorithms 1323 independently. However, the algorithm used MUST provide the router 1324 with a Path-MPR set that fulfills the path coverage criterion, i.e. 1325 it MUST select a Path-MPR set such that for any element of N or N2 1326 that is not in the Path-MPR set, there exists a shortest path that 1327 goes from this element to the router through a neighbor selected as 1328 Path-MPR (unless the shortest path is only one hop). 1330 Appendix C. Contributors 1332 The authors would like to thank Cedric Adjih, Acee Lindem, Padma 1333 Pillay-Esnault and Laurent Viennot for their contributions to this 1334 document. 1336 Appendix D. Acknowledgments 1338 The authors would like to thank Juan Antonio Cordero Fuertes, Ulrich 1339 Herberg and Richard Ogier for reviewing this document. 1341 Authors' Addresses 1343 Emmanuel Baccelli 1344 INRIA 1346 Phone: +33 1 69 33 55 11 1347 EMail: Emmanuel.Baccelli@inria.fr 1348 URI: http://www.emmanuelbaccelli.org/ 1350 Philippe Jacquet 1351 INRIA 1353 Phone: +33 1 3963 5263 1354 EMail: Philippe.Jacquet@inria.fr 1356 Dang-Quan Nguyen 1357 CRC 1359 Phone: +1-613-949-8216 1360 EMail: dang.nguyen@crc.ca 1362 Thomas Heide Clausen 1363 LIX, Ecole Polytechnique, France 1365 Phone: +33 6 6058 9349 1366 EMail: T.Clausen@computer.org 1367 URI: http://www.thomasclausen.org/