idnits 2.17.1 draft-baccelli-ospf-mpr-ext-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 18. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 948. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 959. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 966. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 972. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: 1. If there exists an LSA in the Link State Database, with the same Link State ID, LS Type and Advertizing Router values as the received LSA, and the received LSA is not newer (see section 13.1 of [1]) then the received LSA MUST not be processed EXCEPT for acknowledgement as described in section 5.4. == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: 3. If the scope of the LSA is link local or reserved, the LSA MUST not be flooded on any interface. -- 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 (October 12, 2007) is 6038 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: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: '8' is defined on line 761, but no explicit reference was found in the text ** Obsolete normative reference: RFC 2740 (ref. '2') (Obsoleted by RFC 5340) == Outdated reference: A later version (-06) exists of draft-nguyen-ospf-lls-04 ** Downref: Normative reference to an Experimental draft: draft-nguyen-ospf-lls (ref. '4') == Outdated reference: A later version (-19) exists of draft-ietf-manet-olsrv2-02 Summary: 3 errors (**), 0 flaws (~~), 8 warnings (==), 8 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 Expires: April 14, 2008 D. Nguyen 5 INRIA 6 T. Clausen 7 LIX, Ecole Polytechnique, France 8 October 12, 2007 10 OSPF MPR Extension for Ad Hoc Networks 11 draft-baccelli-ospf-mpr-ext-04 13 Status of this Memo 15 By submitting this Internet-Draft, each author represents that any 16 applicable patent or other IPR claims of which he or she is aware 17 have been or will be disclosed, and any of which he or she becomes 18 aware will be disclosed, in accordance with Section 6 of BCP 79. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note that 22 other groups may also distribute working documents as Internet- 23 Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six months 26 and may be updated, replaced, or obsoleted by other documents at any 27 time. It is inappropriate to use Internet-Drafts as reference 28 material or to cite them other than as "work in progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt. 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 This Internet-Draft will expire on April 14, 2008. 38 Copyright Notice 40 Copyright (C) The IETF Trust (2007). 42 Abstract 44 This document specifies an OSPFv3 interface type tailored for mobile 45 ad hoc networks. This interface type is derived from the broadcast 46 interface type, enhanced with MANET techniques based on multi-point 47 relaying (MPR). 49 Table of Contents 51 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 52 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 53 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 6 54 4. Protocol Overview and Functionning . . . . . . . . . . . . . . 7 55 4.1. Efficient Flooding with MPR . . . . . . . . . . . . . . . 7 56 4.2. MPR Topology Reduction . . . . . . . . . . . . . . . . . . 7 57 4.3. Multicast Transmissions of Protocol Packets . . . . . . . 7 58 4.4. MPR Adjacency Reduction . . . . . . . . . . . . . . . . . 8 59 5. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 9 60 5.1. Data Structures . . . . . . . . . . . . . . . . . . . . . 9 61 5.2. Hello Protocol . . . . . . . . . . . . . . . . . . . . . . 11 62 5.2.1. Flooding MPR Selection . . . . . . . . . . . . . . . . 11 63 5.2.2. Flooding MPR Selection Signalling in HELLO Packets . . 11 64 5.2.3. Neighbor Ordering in HELLO Packets . . . . . . . . . . 11 65 5.2.4. Metric Signalling in HELLO Packets . . . . . . . . . . 12 66 5.2.5. Path MPR Selection . . . . . . . . . . . . . . . . . . 12 67 5.2.6. Path MPR Selection Signalling in HELLO Packets . . . . 12 68 5.2.7. Hello Packet Processing . . . . . . . . . . . . . . . 12 69 5.3. Adjacencies . . . . . . . . . . . . . . . . . . . . . . . 13 70 5.3.1. Protocol Packets over 2-WAY Links . . . . . . . . . . 13 71 5.3.2. Adjacency Conservation . . . . . . . . . . . . . . . . 13 72 5.4. Link State Advertisements . . . . . . . . . . . . . . . . 14 73 5.4.1. LSA Flooding . . . . . . . . . . . . . . . . . . . . . 14 74 5.4.2. Link State Acknowlements . . . . . . . . . . . . . . . 15 75 6. Security Considerations . . . . . . . . . . . . . . . . . . . 17 76 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 77 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 78 8.1. Normative References . . . . . . . . . . . . . . . . . . . 21 79 8.2. Informative References . . . . . . . . . . . . . . . . . . 21 80 Appendix A. Flooding MPR Selection Heuristic . . . . . . . . . . 22 81 Appendix B. Path MPR Selection Heuristic . . . . . . . . . . . . 24 82 Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 83 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 27 84 Intellectual Property and Copyright Statements . . . . . . . . . . 28 86 1. Introduction 88 This document specifies an extension of OSPFv3 [2] adapted to MANETs 89 [6], based on mechanisms providing: 91 - Flooding reduction: a mechanism reducing the number of 92 (re)transmissions during floods. 94 - Topology reduction: a mechanism reducing the number and the size 95 of LSAs, by advertizing only a subset of the existing links. 97 - Adjacency reduction: a mechanism reducing the database 98 synchronization overhead by bringing up only selected adjacencies. 100 These mechanisms are based on multipoint relaying (MPR), a technique 101 developed in OLSR, the proactive routing solution standardized in 102 MANET [5] [7]. 104 The extension specified in this document integrates the OSPF 105 framework by defining an OSPF interface type: the MANET interface. 106 While this extension enables OSPF to function efficiently on mobile 107 ad hoc networks, operation of OSPF on other types of interfaces or 108 networks remains unaltered, whether there are MANET interfaces in the 109 area or not. 111 2. Terminology 113 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 114 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 115 document are to be interpreted as described in RFC2119 [3]. 117 Additionally, this document uses traditional OSPF terminology as 118 defined in [1] [2], LLS terminology as defined in [4], as well as the 119 following terms: 121 MANET interface - the OSPF interface type for MANETs, specified in 122 this document. 124 MANET router - a router which has only MANET interface(s). 126 Wired router - a router which only has OSPF interface(s) of types 127 other than MANET. 129 Hybrid router - a router which has OSPF interfaces of several types, 130 including the MANET type. 132 Neighbor - a router, reachable through an OSPF interface (of any 133 type). 135 MANET neighbor - a neighbor, reachable through an OSPF interface of 136 type MANET. 138 Symmetric neighbor - a neighbor, in a state greater than or equal to 139 2-Way (through an interface of any type). 141 Symmetric 2-hop neighbor - a symmetric neighbor of a symmetric 142 neighbor, which is not a neighbor of the considered router. 144 Neighborhood - the set formed by the symmetric neighbors of the 145 considered router. 147 2-hop neighborhood - the set formed by all the symmetric 2-hop 148 neighbors of the considered router. 150 Synch router - a router which brings up adjacencies with all its 151 MANET neighbors. 153 Flooding MPR set - the subset of symmetric neighbors selected as 154 flooding MPR by this router. 156 Flooding MPR selector set - the subset of symmetric neighbors that 157 have selected this router as flooding MPR. 159 Path MPR set - the subset of symmetric neighbors selected as path 160 MPR by this router. 162 Path MPR selector set - the subset of symmetric neighbors that have 163 selected this router as path MPR. 165 MPR (selector) set - the union of the flooding MPR (selector) set 166 and the path (selector) MPR set of this router. 168 3. Applicability Statement 170 Characteristics of MANETs include mobility and "half-broadcast" 171 capabilities [9], i.e., a router that makes a transmission on a MANET 172 can only assume that a subset of the routers attached to the MANET 173 will hear this transmission. In particular, these characteristics 174 are not compatible with several traditional OSPF mechanisms, 175 including some reducing the amount of control traffic, such as 176 flooding reduction, topology reduction and adjacency reduction (e.g. 177 Designated Router). However, OSPF's efficient operation over MANETs 178 relies on drastic control traffic reduction, as wireless links 179 generally feature bandwidth scarcity and interference issues. 181 The MANET interface type enables OSPF operation on mobile ad hoc 182 networks, by providing specific flooding reduction, topology 183 reduction and adjacency reduction mechanisms adapted to MANET 184 characteristics. These mechanisms are derived from solutions 185 standardized by the MANET working group. However, while MANET 186 standards address optimized ad hoc routing solutions for truely 187 mobile enviromnents, OSPF's extension for ad hoc networks addresses 188 less mobile scenarios, that possibly include parts of the network 189 that are fixed, using solely the traditional OSPF framework. 191 4. Protocol Overview and Functionning 193 This document specifies an OSPFv3 interface type tailored for mobile 194 ad hoc networks: the MANET interface. 196 The MANET interface makes use of flooding reduction, topology 197 reduction and adjacency reduction mechanisms based on multipoint 198 relaying (MPR), a technique derived from OLSR [5] [7], the proactive 199 routing solution standardized in MANET. 201 4.1. Efficient Flooding with MPR 203 MANET interfaces use a flooding reduction mechanism called MPR 204 flooding, whereby only some MANET neighbors (those selected as 205 flooding-MPR) are responsible for retransmitting a routing packet 206 flooded over a MANET interface. This mechanism drastically reduces 207 the number of (re)transmissions during flooding procedures, while 208 still providing a natural high resilience to transmission errors 209 (inherent to the use of wireless links), and obsolete two-hop 210 neighbor information (frequently caused by the mobility of the 211 routers). 213 4.2. MPR Topology Reduction 215 MANET interfaces use a topology reduction mechanisms called MPR 216 topology reduction, whereby only necessary wireless links to MANET 217 neighbors (those concerned by path-MPR selection, as belonging to 218 shortest paths) are listed in LSAs. MANET routers periodically 219 generate and flood Router-LSAs describing their selection of wireless 220 links to (current) MANET neighbors as point-to-point links. This 221 mechanism greatly reduces the size of LSAs originated by MANET 222 routers, while still keeping OSPF's traditional properties: optimal 223 paths using synchronized adjacencies. 225 4.3. Multicast Transmissions of Protocol Packets 227 In order to reduce the overehead, multicast is used as much as 228 possible for protocol packet transmissions over MANET interfaces, 229 taking advantage of broadcast capabilities of the wireless medium 230 [9]. In particular, LSA acknowledgements are sent via multicast over 231 these interfaces, and retransmissions over the same interfaces are 232 considered as implicit acknowledgements. Intelligent jitter 233 management delaying packets' (re)transmissions may also be used to 234 increase the chance to bundle several packets in a single 235 transmission, or to avoid superfluous retransmissions due to packet 236 collisions (see [10]). 238 4.4. MPR Adjacency Reduction 240 Furthermore, MANET routers may form adjacencies with a subset of 241 their MANET neighbors (instead of all of them). However, no 242 Designated Router or Backup Designated Router is elected on an OSPF 243 MANET. Instead, most MANET routers bring up adjacencies only with 244 their MPR and MPR selectors, while some select MANET routers (called 245 Synch routers) must bring up adjacencies with all their MANET 246 neighbors. This reduces the amount of control traffic needed for 247 database synchronization, while ensuring that LSAs still describe 248 synchronized adjacencies only. 250 5. Protocol Details 252 This section specifies the information that must be maintained, 253 processed and transmitted by MANET and hybrid routers, and 254 complements RFC 2740 [2]. 256 5.1. Data Structures 258 In addition to the values used in RFC 2740 [2], the type field in the 259 interface data structure can take a new value, "MANET". Furthermore, 260 in addition to the protocol structures defined by RFC 2740 [2], MANET 261 and hybrid routers make use of the data structures described below. 263 N : 265 the router IDs of the set of symmetric neighbors of the router. 266 More precisely, N lists tuples of the form (1_HOP_SYM_id, 267 1_HOP_SYM_time). 1_HOP_SYM_id is the router ID of the symmetric 268 neighbor. 1_HOP_SYM_time specifies the time, at which the tuple 269 expires and MUST be removed from the set. 271 N2 : 273 the router IDs of the set of symmetric neighbors of routers that 274 are in N, excluding: 276 (i) the router performing the computation 278 (ii) all routers in N. 280 More precisely, N2 lists tuples of the form (2_HOP_SYM_id, 281 1_HOP_SYM_id, 2_HOP_SYM_time). 2_HOP_SYM_id is the router ID of a 282 symmetric 2-hops neighbor. 1_HOP_SYM_id is the router ID of the 283 symmetric neighbor through which the 2-hop neighbor can be 284 reached. 2_HOP_SYM_time specifies the time, at which the tuple 285 expires and MUST be removed from the set. 287 Flooding-MPR set: 289 the router IDs of a subset of the routers listed in N, selected 290 such that through this subset, each router listed in N2 is 291 reachable. These neighbors are said to have been "selected as 292 flooding MPR" by the router. More precisely, the Flooding-MPR set 293 lists tuples of the form (Flooding_MPR_id, Flooding_MPR_time). 294 Flooding_MPR_id is the router ID of the symmetric neighbor 295 selected as flooding MPR. Flooding_MPR_time specifies the time, 296 at which the tuple expires and MUST be removed from the set. For 297 details about MPR selection, see Section 5.2. 299 Flooding-MPR-selector set: 301 the router IDs of the set of neighbors that have selected the 302 router as flooding MPR. More precisely, the Flooding-MPR-selector 303 set lists tuples of the form (Flooding_MPR_SELECTOR_id, 304 Flooding_MPR_SELECTOR_time). Flooding_MPR_SELECTOR_id is the 305 router ID of the symmetric neighbor that has selected the router 306 as flooding MPR. Flooding_MPR_SELECTOR_time specifies the time at 307 which the tuple expires and MUST be removed from the set. For 308 details about Flooding MPR selection, see Section 5.2. 310 Path-MPR set: 312 the router IDs of a subset of the routers listed in N that provide 313 shortest paths from the members of N2 to the router. These 314 neighbors are said to have been "selected as path MPR" by the 315 router. More precisely, the Path-MPR set lists tuples of the form 316 (Path_MPR_id, Path_MPR_time). Path_MPR_id is the router ID of the 317 symmetric neighbor selected as path MPR. Path_MPR_time specifies 318 the time at which the tuple expires and MUST be removed from the 319 set. For details about path MPR selection, see Section 5.2. 321 Path-MPR-selector set : 323 the router IDs of the set of neighbors that have selected the 324 router as path MPR. More precisely, the Path-MPR-selector set 325 lists tuples of the form (Path_MPR_SELECTOR_id, 326 Path_MPR_SELECTOR_time). Path_MPR_SELECTOR_id is the router ID of 327 the symmetric neighbor that has selected the router as path MPR. 328 Path_MPR_SELECTOR_time specifies the time at which the tuple 329 expires and MUST be removed from the set. For details about path 330 MPR selection, see Section 5.2. 332 5.2. Hello Protocol 334 On MANET interfaces, packets are sent, received and processed as 335 defined by RFC 2740 [2] and RFC 2328 [1], with the following 336 additions for MPR selection as described in this section. 338 5.2.1. Flooding MPR Selection 340 The objective of flooding MPR selection is for a router to select a 341 subset of its neighbors such that a packet, retransmitted by these 342 selected neighbors, will be received by all routers 2 hops away. 343 This property is called the flooding MPR "coverage criterion". The 344 flooding MPR set of a router is computed such that, for each 345 interface, it satisfies this criterion. The information required to 346 perform this calculation (i.e. link sensing and neighborhood 347 information) is acquired through periodic exchange of OSPF HELLO 348 packets. 350 Flooding MPRs are computed by each MANET or hybrid router. The 351 smaller the flooding MPR set is, the lower the overhead will be. 352 However, while it is not essential that the flooding MPR set is 353 minimal, it is essential that all 2-hop neighbors can be reached 354 through the selected flooding MPR routers. A router MUST select a 355 flooding MPR set such that any 2-hop neighbor is covered by at least 356 one flooding MPR router. 358 Flooding MPR selection priority may be given to neighbor routers in 359 descending order of their willingness to flood traffic on behalf of 360 other routers. Appendix A gives a heuristic for flooding MPR 361 selection. 363 5.2.2. Flooding MPR Selection Signalling in HELLO Packets 365 A router that has selected flooding MPRs among its neighbors MUST 366 signal this selection through appending LLS information (TLV type 3) 367 at the end of its HELLO packets as described in Section 7. This 368 information signals the list of neighbors the router has selected as 369 flooding MPR, and the willingness of the router to be flooding 370 traffic on behalf of other routers. 372 5.2.3. Neighbor Ordering in HELLO Packets 374 Neighbors listed in the HELLO packets sent over MANET interfaces MUST 375 be listed such that symmetric neighbors are listed before other 376 neighbors. Moreover, neighbors selected as flooding MPR MUST be 377 listed before other symmetric neighbors. This specific ordering 378 corresponds with LLS information (TLV type 3) appended to the HELLO 379 packet, as described in Section 7. 381 5.2.4. Metric Signalling in HELLO Packets 383 HELLO packets sent over MANET interfaces MUST advertize the costs of 384 links towards ALL its symmetric MANET neighbors. If the router has 385 several MANET interfaces, links to ALL the symmetric MANET neigbors 386 over ALL the MANET interfaces of the router MUST have their costs 387 listed. The costs of the links from the router to its neighbors as 388 well as from the neighbors to the router (the reverse costs) are 389 specified using the LLS format (TLV type 4) described in Section 7, 390 appended at the end of Hello packets. 392 5.2.5. Path MPR Selection 394 Using the LLS metric information included in HELLO packets, a MANET 395 router MUST identify a subset of its links to neighbors that are on 396 shortest paths with respect to the metric in use. This mechanism is 397 called Path MPR selection. Appendix B gives a heuristic for path MPR 398 selection. 400 Hybrid routers MUST select ALL their MANET and hybrid neighbors as 401 path MPRs. MANET routers MAY select a subset of MANET neighbors as 402 path MPR. However a MANET router MUST ensure that for each element 403 of N or N2 that is not in the path MPR set, there exists a shortest 404 path that goes from this element to the router through a neighbor 405 selected as path MPR (unless the shortest path is only one hop, of 406 course). 408 5.2.6. Path MPR Selection Signalling in HELLO Packets 410 A router that has selected path MPRs among its neighbors MUST signal 411 this selection through appended LLS information (TLV type 4) at the 412 end of its HELLO packets as described in Section 7. This information 413 signals the list of neighbors the router has selected as path MPR. 414 Neighbors listed in the TLV type 4 MUST be listed such that adjacent 415 neighbors are listed before other neighbors. Moreover, neighbors 416 selected as path MPR MUST be listed before other adjacent neighbors. 418 5.2.7. Hello Packet Processing 420 In addition to the processing specified by RFC 2740 [2], N and N2 421 MUST be updated when received HELLO packets signal changes in the 422 neighborhood of a MANET interface. The flooding MPR set and the path 423 MPR set MUST then be recomputed if N or N2 have changed. 425 Moreover, the flooding MPR selector set and the path MPR selector set 426 MUST be updated upon receipt of a HELLO packet containing LLS 427 information signalling change in the list of neighbors that has 428 selected the router as MPR. 430 5.3. Adjacencies 432 When adjacencies are brought up between MANET and hybrid neighbors, 433 procedure goes on as defined in RFC 2740 [2] and RFC 2328 [1]. 434 However, in order to further reduce the control traffic overhead on 435 the wireless medium, MANET routers MAY bring up adjacencies with a 436 subset of their MANET or hybrid neighbors. 438 Over a MANET interface, a router MUST bring up adjacencies with the 439 neighbors it has included in its MPR set and its MPR Selector set. 441 Some routers (called synch routers) MUST bring up adjacencies with 442 other MANET neighbors as well. Other routers MAY bring up 443 adjacencies with MANET neighbors other than MPRs and MPR selectors, 444 at the expense of more synchronisation overhead. The proposed 445 heuristic for routers to decide whether they are a synch router is as 446 follows: 448 o a MANET router decides it is a synch router if and only if the 449 router has a higher ID than any other ID present in Hello packets 450 or Router-LSAs it has received from other reachable routers in the 451 area. 453 Other algorithms are possible. However, algorithms MUST ensure that 454 if there are no hybrid routers in the MANET, at least one router in 455 the MANET selects itself as synch router. Moreover, a MANET router 456 that selects itself as synch router MUST signal this by setting the S 457 bit in the TLV type 4 appended to the Hello packets it generates, as 458 described in Section 7. 460 5.3.1. Protocol Packets over 2-WAY Links 462 When a router does not form a FULL adjacency with a MANET neighbor, 463 the state does not progress beyond 2-WAY (as defined in RFC 2740 [2] 464 and RFC 2328 [1]). A MANET interface MAY send routing protocol 465 packets while in 2-WAY state. 467 Therefore, any routing protocol packet received from a symmetric 468 MANET neighbor MUST be processed. Similar to the OSPF broadcast 469 interface [1], the next hop in the forwarding table MAY be a neighbor 470 that is not adjacent. However, when a data packet has travelled 471 beyond its first hop, the MPR selection process guarantees that 472 subsequent hops in the SPT will be over adjacencies. 474 5.3.2. Adjacency Conservation 476 Adjacencies are torn down as defined in RFC 2740 [2] and RFC 2328 477 [1]. This means that when the MPR set or MPR selector set is updated 478 (due to changes in the neighborhood), and when a neighbor was 479 formerly, but is no longer, in the MPR set or the MPR selector set, 480 the adjacency with this neighbor is kept, unless it is no longer a 481 symmetric neighbor. 483 When a router receives Hello packets from a symmetric neighbor which 484 cease to list the router as being adjacent (see Section 5.2.3), the 485 state of this neighbor MUST be changed to (i) 2-WAY if the neighbor 486 is not in the MPR set or the MPR selector set, or (ii) ExStart if the 487 neighbor is in the MPR set or the MPR selector set, or if the 488 neighbor or the router itself is a synch router. 490 5.4. Link State Advertisements 492 The Router-LSAs originated by a hybrid router list adjacencies over 493 interfaces other than MANET as specifed in RFC 2740 [2] and RFC 2328 494 [1]. Hybrid and MANET routers MUST list in the Router-LSAs they 495 originate the links to the neighbors that are in their Path MPR set 496 and their Path MPR Selector set. MANET routers MAY list other links 497 they have through MANET interfaces, to the expense of more overhead. 499 Hybrid and MANET routers MUST flood updated Router-LSAs when a new 500 adjacency has been brought up reflecting change in the MPR set (or 501 the MPR Selector set), and when a neighbor formerly listed in 502 originated LSAs is no longer adjacent. 504 5.4.1. LSA Flooding 506 LSUpdates received on an interface of a type other than MANET are 507 processed and flooded as specified in [1] and [2], over every 508 interface. If an LSUpdate was received on a MANET interface, it is 509 processed as follows, with regards to flooded LSAs. 511 1. Consistency checks are made on the received packet, as specified 512 in [1] and [2], before being handed to the procedure described in 513 the following steps, and the Link State Update packet is thus 514 associated with a particular neighbor and a particular area. 516 2. If the LSU was received from a router other than a symmetric 517 neighbor, the LSUpdate MUST be discarded without further 518 processing. Otherwise, for each LSA contained in LSUpdates 519 received on MANET interfaces, the following steps replace steps 1 520 to 5 of section 13.3 of [1]. 522 1. If there exists an LSA in the Link State Database, with the 523 same Link State ID, LS Type and Advertizing Router values as 524 the received LSA, and the received LSA is not newer (see 525 section 13.1 of [1]) then the received LSA MUST not be 526 processed EXCEPT for acknowledgement as described in section 527 5.4. 529 2. Otherwise, the LSA MUST be attributed a scope according to 530 its type, as specified in section 3.5 of [2]. 532 3. If the scope of the LSA is link local or reserved, the LSA 533 MUST not be flooded on any interface. 535 4. Otherwise: 537 - If the scope of the LSA is the area, the LSA MUST be 538 flooded on all the interfaces of the router in that area 539 according to the default flooding algorithm described below. 541 - Otherwise, the LSA MUST be flooded on all the interfaces of 542 the router according to the default flooding algorithm 543 described below. 545 The default flooding algorithm is then the following: 547 1. The LSA MUST be installed in the Link State Database. 549 2. The Age of the LSA is increased by InfTransDelay. 551 3. The LSA is flooded over all interfaces of type other than MANET. 553 4. If the sender interface address is an interface address of an 554 flooding MPR selector of this router, the LSA MUST also be 555 retransmitted out all MANET interfaces concerned by the scope, 556 with the multicast address all_SPF_Routers. 558 Note that MinLSArrival SHOULD be set to a value that is appropriate 559 to MANET dynamic topologies: LSA updating may need to be more 560 frequent in MANET parts of the OSPF network than in traditional parts 561 of the OSPF network. 563 5.4.2. Link State Acknowlements 565 When a router receives an LSA on a MANET interface, the router MUST 566 proceed to acknowledge the LSA as follows 568 1. If the LSA was not received from an adjacent neighbor, the router 569 MUST NOT acknowledge it. 571 2. Otherwise, if the LSA was received from an adjacent neighbor if 572 the LSA is already in the database (i.e. the LSA has already been 573 received and processed) the router MUST send an acknowledgement 574 for this LSA on all MANET interfaces, to the multicast address 575 all_SPF_Routers. 577 3. Otherwise, if the LSA is not already in the database: 579 1. If the router decides to retransmit the LSA (as part of the 580 flooding procedure), the router MUST NOT acknowledge it, as 581 this retransmission will be considered as an implicit 582 acknowledgement. 584 2. Otherwise, if the router decides to not retransmit the LSA 585 (as part of the flooding procedure), the router MUST send an 586 acknowledgement for this LSA on all MANET interfaces, to the 587 multicast address all_SPF_Routers. 589 If a router sends an LSA on a MANET interface, it expects 590 acknowledgements (explicit or implicit) from each adjacent neighbors. 591 In the case where the router did not originate the LSA (i.e. relays 592 the LSA), the router MUST only expect acknowledgements (explicit or 593 implicit) from adjacent neighbors that have not previously 594 acknowledged this LSA. If a router detects that some adjacent 595 neighbor has not acknowledged the LSA, the router retransmits the 596 LSA. 598 If, due to efficient flooding procedure decision, a router decides to 599 not relay an LSA, the router MUST still expect acknowledgements of 600 that LSA (explicit or implicit) from adjacent neighbors that have not 601 previously acknowledged this LSA. If a router detects that some 602 adjacent neighbor has not acklnowledged the LSA, the router 603 retransmits the LSA. 605 Note that it may be beneficial to aggregate several acknowledgements 606 in the same transmission, taking advantage of multicasting. A timer 607 wait MAY thus be used before any acknowledgement transmission in 608 order to avoid multiple OSPF acknowledgement transmissions. 610 Additional jitter delay in packet (re)transmission may be used in 611 order to increase the opportunities to bundle several packets 612 together per transmission (which provides a reduction in the number 613 of overall transmissions, and therefore the number of collisions over 614 the wireless media). 616 6. Security Considerations 618 This document does currently not specify security considerations. 620 7. IANA Considerations 622 This document defines the new TLV types below, to be allocated by 623 IANA. 625 OSPF packets sent by MANET and hybrid routers are formated as defined 626 by RFC2740 [2] and RFC2328 [1]. The LLS extension [4] is used in 627 HELLO packets sent over MANET interfaces, as follows. 629 The Hello packets sent over an OSPF MANET interface have the L bit 630 set. An LLS datablock containing flooding MPR selection information 631 is appended to these Hello messages. The TLV of Type 3 is defined as 632 the flooding MPR selection TLV type shown in Fig. 1. 634 0 1 2 3 635 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 636 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 637 | Type=3 | Length | 638 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 639 | Willingness | # Sym. Neigh. | # MPR | Reserved | 640 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 642 Fig. 1 : Flooding MPR selection (TLV type 0) 644 Willingness 646 This field specifies the willingness of the router to flood link 647 state information on behalf of other routers. It can be set to 648 any integer value from 1 to 6. By default, a router SHOULD 649 advertise a willingness of WILL_DEFAULT = 3. 651 # Sym. Neigh. 653 Number of symmetric neighbors, listed first among the neighbors in 654 a HELLO packet. 656 # MPR 658 Number of neighbors, listed first among the symmetric neighbors on 659 this interface in a HELLO packet, that are selected by the router 660 as flooding MPR. 662 Reserved 664 This 8 bits long field is set to 0 by the sender and ignored by 665 the receiver. 667 In addition to flooding MPR TLVs, HELLO packets contain an appended 668 path MPR selection TLV defined as the TLV type 4 shown in Fig. 2. 670 0 1 2 3 671 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 672 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 673 | Type=4 | Length | 674 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 675 | # Adj. Neigh | # Path MPR |S| Reserved | 676 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 677 | Neighbor ID | 678 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 679 | Cost | Reverse Cost | 680 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 681 | Neighbor ID | 682 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 683 | Cost | Reverse Cost | 684 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 685 : : 686 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 688 Fig. 2 : metric advertisement (TLV type 1) 690 # Adj. Neigh 692 Number of blocks (Neighbor ID, Cost, Reverse Cost), listed first 693 in the TLV, that describe adjacent MANET neighbors. 695 # Path MPR 697 Number of blocks (Neighbor ID, Cost, Reverse Cost), listed first 698 among the blocks concerning adjacent MANET neighbors, that 699 describe MANET neighbors that are selected as path MPRs by the 700 router. 702 S bit 704 This bit is set to 1 if the router decides it is a synch router. 705 Otherwise it is set to 0. 707 Reserved 709 This field is 16 bits long and must be set to 0 to be in 710 compliance with this specification. 712 Neighbor ID 714 This field specifies the router ID of a MANET neighbor. 716 Cost 718 This field specifies the cost of the link going from the router 719 towards the neighbor indicated in the neighbor ID field. If a 720 neighbor is reachable through several interfaces at the same time, 721 the advertized cost is set to the minimum of the costs over these 722 different interfaces. 724 Reverse Cost 726 This field specifies the cost of the link going from the neighbor 727 indicated in the neighbor ID field towards the router. By default 728 it is set to 0xFFFF (maximal value, i.e. infinity), unless 729 information received via HELLO packets from the neighbor specifies 730 otherwise. If a neighbor is reachable through several interfaces 731 at the same time, the advertized cost is set to the minimum of the 732 costs over these different interfaces. 734 8. References 736 8.1. Normative References 738 [1] Moy, J., "OSPF version 2", RFC 2328, 1998. 740 [2] Moy, J., Coltun, R., and D. Ferguson, "OSPF for IPv6", 741 RFC 2740, 1999. 743 [3] Bradner, S., "Key words for use in RFCs to Indicate Requirement 744 Levels", RFC 2119, 1997. 746 [4] Zinin, A., Friedman, B., Roy, A., Nguyen, L., and D. Yeung, 747 "OSPF Link Local Signaling", draft-nguyen-ospf-lls-04 (work in 748 progress), 2004. 750 8.2. Informative References 752 [5] Clausen, T. and P. Jacquet, "The Optimized Link State Routing 753 Protocol", RFC 3626, October 2003. 755 [6] Macker, J. and S. Corson, "MANET Routing Protocol Performance 756 Issues and Evaluation Considerations", RFC 2501, January 1999. 758 [7] OLSRv2, Design Team., "OLSR version 2", 759 draft-ietf-manet-olsrv2-02 (work in progress), June 2006. 761 [8] Ngyuen, D. and P. Minet, "Analysis of MPR Selection in the OLSR 762 Protocol", 2nd Int. Workshop on Performance Analysis and 763 Enhancement of Wireless Networks , 2007. 765 [9] Macker, J., Chakeres, I., and T. Clausen, "Mobile Ad hoc 766 Network Architecture", ID draft-ietf-autoconf-manetarch, 767 February 2007. 769 [10] Adamson, B., Dearlove, C., and T. Clausen, "Jitter 770 Considerations in MANETs", ID draft-ietf-manet-jitter, 771 June 2007. 773 Appendix A. Flooding MPR Selection Heuristic 775 The following specifies a proposed heuristic for selection of 776 flooding MPRs. It constructs a flooding MPR set that enables a 777 router to reach routers in the 2-hop neighborhood through relaying by 778 one flooding MPR router. 780 The following terminology will be used in describing the heuristics: 781 D(y) is the degree of a 1-hop neighbor router y (where y is a member 782 of N), defined as the number of neighbors of router y, EXCLUDING all 783 the members of N and EXCLUDING the router performing the computation. 784 The proposed heuristic can then be described as follows. Begin with 785 an empty flooding MPR set. Then: 787 1. Calculate D(y), where y is a member of N, for all routers in N. 789 2. Add to the flooding MPR set those routers in N, which are the 790 only routers to provide reachability to a router in N2. For 791 example, if router b in N2 can be reached only through a router a 792 in N, then add router a to the flooding MPR set. Remove the 793 routers from N2 which are now covered by a router in the flooding 794 MPR set. 796 3. While there exist routers in N2 which are not covered by at least 797 one router in the flooding MPR set: 799 1. For each router in N, calculate the reachability, i.e. the 800 number of routers in N2 which are not yet covered by at least 801 one router in the flooding MPR set, and which are through 802 this 1-hop neighbor; 804 2. Select as a flooding MPR the neighbor with highest 805 willingness among the routers in N with non-zero 806 reachability. In case of a tie among routers with same 807 willingness the router which provides reachability to the 808 maximum number of routers in N2. In case of another tie 809 between routers also providing the same amount of 810 reachability, select as flooding MPR the router whose D(y) is 811 greater. Remove the routers from N2 which are now covered by 812 a router in the flooding MPR set. 814 4. As an optimization, process each router, y, in the flooding MPR 815 set in increasing order of willingness. If all routers in N2 are 816 still covered by at least one router in the flooding MPR set 817 excluding router y, then router y MAY be removed from the 818 flooding MPR set. 820 Other algorithms, as well as improvements over this algorithm, are 821 possible. Different routers may use different algorithms 822 independently. The only requirement is that the algorithm used by a 823 given router MUST provide the router with an MPR set that fulfills 824 the MPR flooding coverage criterion, i.e. it MUST select a flooding 825 MPR set such that any 2-hop neighbor is covered by at least one 826 flooding MPR router. 828 Appendix B. Path MPR Selection Heuristic 830 The following specifies a proposed heuristic for selection of path 831 MPRs. It constructs a path MPR-set that enables a router to reach 832 routers in the 2-hop neighborhood through shortest paths via routers 833 in its path MPR-set. The following terminology will be used: 835 - The router where the computation is done will be called A. 837 - For a router B neighbor of A, cost(A,B) is the cost of the path 838 through the direct link, from A to B, and this is an entry in the 839 router cost matrix defined below. 841 - For a router C in the neighborhood or 2-hop neighborhood of A, 842 dist(C,A) is the cost of the shortest path from C to A and this is 843 an entry in the router distance vector defined below. 845 The cost matrix is populated with the values of the costs of links 846 originating from router A (available locally) and by values listed in 847 Hello packets received from neighbor routers. More precisely, the 848 cost matrix is populated as follows: 850 1. The coefficients of the cost matrix are set by default to 0xFFFF 851 (maximal value, i.e. infinity). 853 2. The coefficient cost(A,B) of the cost matrix for a link from 854 router A to a neighbor B (the direct cost for this link) is set 855 to the minimum cost over all interfaces that feature router B as 856 a symmetric neighbor. The reverse cost for this link, cost(B,A), 857 is set at the value received in Hello packets from router B. If 858 router B is reachable through several interfaces at the same 859 time, cost(B,A) is set as the minimum cost advertized by router B 860 for its links towards router A. 862 3. The coefficients of the cost matrix concerning the link between 863 two neighbors of A, routers C and B, are populated at the 864 reception of their Hello packets. The cost (B,C) is set to the 865 value advertized by the Hello packets from B, and respectively, 866 the cost (C,B) is set to the value advertised in Hello packets 867 from C. 869 4. The coefficients of the cost matrix, cost(B,C) for a link that 870 connects a neighbor B to a 2-hop neighbor C is obtained via the 871 Hello packets received from router B. In this case cost(B,C) and 872 cost(C,B) are respectively set to the values advertized by router 873 B for the direct cost and reverse cost for node C. 875 Once the cost matrix is populated, the proposed heuristic can then be 876 described as follows. Begin with an empty path MPR set. Then: 878 1. Using the cost matrix and the Dijkstra algorithm, compute the 879 router distance vector, i.e. the shortest distance for each pair 880 (X,A) where X is in N or N2 minimizing the sum of the cost of the 881 path between X and A. 883 2. Compute N' as the subset of N made of the elements X such that 884 cost(X,A)=dist(X,A). 886 3. Compute N2' as the subset of N and N2 made of the elements Y that 887 do not belong to N' and such that there exist X in N' such 888 cost(Y,X)+cost(X,A)=dist(Y,A). 890 4. Compute the MPR selection algorithm presented in Appendix A with 891 N' instead of N and N2' instead of N2. The resulting MPR set is 892 the path MPR set. 894 Other algorithms, as well as improvements over this algorithm, are 895 possible. Different routers may use different algorithms 896 independently. However, a MANET router MUST ensure that for each 897 element of N or N2 that is not in the path MPR set, there exists a 898 shortest path that goes from this element to the router through a 899 neighbor selected as path MPR (unless the shortest path is only one 900 hop). 902 Contributors 904 The authors thank Cedric Adjih, Acee Lindem, Padma Pillay-Esnault and 905 Laurent Viennot for their contributions to this document. 907 Authors' Addresses 909 Emmanuel Baccelli 910 INRIA 912 Phone: +33 1 69 33 55 11 913 Email: Emmanuel.Baccelli@inria.fr 915 Philippe Jacquet 916 INRIA 918 Phone: +33 1 3963 5263 919 Email: Philippe.Jacquet@inria.fr 921 Dang-Quan Nguyen 922 INRIA 924 Phone: +33 1 3963 5511 925 Email: Dang-Quan.Nguyen@inria.fr 927 Thomas Heide Clausen 928 LIX, Ecole Polytechnique, France 930 Phone: +33 6 6058 9349 931 Email: T.Clausen@computer.org 932 URI: http://www.lix.polytechnique.fr/Labo/Thomas.Clausen/ 934 Full Copyright Statement 936 Copyright (C) The IETF Trust (2007). 938 This document is subject to the rights, licenses and restrictions 939 contained in BCP 78, and except as set forth therein, the authors 940 retain all their rights. 942 This document and the information contained herein are provided on an 943 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 944 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 945 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 946 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 947 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 948 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 950 Intellectual Property 952 The IETF takes no position regarding the validity or scope of any 953 Intellectual Property Rights or other rights that might be claimed to 954 pertain to the implementation or use of the technology described in 955 this document or the extent to which any license under such rights 956 might or might not be available; nor does it represent that it has 957 made any independent effort to identify any such rights. Information 958 on the procedures with respect to rights in RFC documents can be 959 found in BCP 78 and BCP 79. 961 Copies of IPR disclosures made to the IETF Secretariat and any 962 assurances of licenses to be made available, or the result of an 963 attempt made to obtain a general license or permission for the use of 964 such proprietary rights by implementers or users of this 965 specification can be obtained from the IETF on-line IPR repository at 966 http://www.ietf.org/ipr. 968 The IETF invites any interested party to bring to its attention any 969 copyrights, patents or patent applications, or other proprietary 970 rights that may cover technology that may be required to implement 971 this standard. Please address the information to the IETF at 972 ietf-ipr@ietf.org. 974 Acknowledgment 976 Funding for the RFC Editor function is provided by the IETF 977 Administrative Support Activity (IASA).