idnits 2.17.1 draft-ietf-ospf-manet-mdr-00.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 16. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 2928. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 2905. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 2912. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 2918. 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 Copyright Line does not match the current year == Line 2450 has weird spacing: '... Router inte...' -- 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 (February 17, 2008) is 5906 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 2740 (Obsoleted by RFC 5340) == Outdated reference: A later version (-08) exists of draft-ietf-ospf-lls-03 Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group R. Ogier 3 Internet-Draft SRI International 4 Intended status: Experimental P. Spagnolo 5 Expires: August 17, 2008 Boeing 6 February 17, 2008 8 MANET Extension of OSPF using CDS Flooding 9 draft-ietf-ospf-manet-mdr-00.txt 11 Status of this Memo 13 By submitting this Internet-Draft, each author represents that any 14 applicable patent or other IPR claims of which he or she is aware 15 have been or will be disclosed, and any of which he or she becomes 16 aware will be disclosed, in accordance with Section 6 of BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/1id-abstracts.html 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html 33 This Internet-Draft will expire on August 17, 2008. 35 Copyright Notice 37 Copyright (C) The IETF Trust (2008). 39 Abstract 41 This document specifies an extension of OSPF for IPv6 to support 42 mobile ad hoc networks (MANETs). The extension, called OSPF-MDR, is 43 designed as a new OSPF interface type for MANETs. OSPF-MDR is based 44 on the selection of a subset of MANET routers, consisting of MANET 45 Designated Routers (MDRs) and Backup MDRs. The MDRs form a connected 46 dominating set (CDS), and the MDRs and Backup MDRs together form a 47 biconnected CDS for robustness. This CDS is exploited in two ways. 48 First, to reduce flooding overhead, an optimized flooding procedure 49 is used in which only (Backup) MDRs flood new LSAs back out the 50 receiving interface; reliable flooding is ensured by retransmitting 51 LSAs along adjacencies. Second, adjacencies are formed only between 52 (Backup) MDRs and a subset of their neighbors, allowing for much 53 better scaling in dense networks. The CDS is constructed using 2-hop 54 neighbor information provided in a Hello protocol extension. The 55 Hello protocol is further optimized by allowing differential Hellos 56 that report only changes in neighbor states. Options are specified 57 for originating router-LSAs that provide full or partial topology 58 information, allowing overhead to be reduced by advertising less 59 topology information. 61 Table of Contents 63 1 Introduction ................................................. 4 64 1.1 Terminology .................................................. 5 65 2 Overview ..................................................... 7 66 2.1 Selection of MDRs, BMDRs, Parents, and Adjacencies ........... 7 67 2.2 Flooding Procedure ........................................... 9 68 2.3 Link State Acknowledgments ................................... 9 69 2.4 Routable Neighbors ........................................... 9 70 2.5 Partial and Full Topology LSAs .............................. 10 71 2.6 Hello Protocol .............................................. 11 72 3 Interface and Neighbor Data Structures ...................... 11 73 3.1 Changes to Interface Data Structure ......................... 11 74 3.2 New Configurable Interface Parameters ....................... 12 75 3.3 Changes to Neighbor Data Structure .......................... 14 76 4 Hello Protocol .............................................. 16 77 4.1 Sending Hello Packets ....................................... 16 78 4.2 Receiving Hello Packets ..................................... 19 79 4.3 Neighbor Acceptance Condition ............................... 22 80 5 MDR Selection Algorithm ..................................... 23 81 5.1 Phase 1: Creating the Neighbor Connectivity Matrix .......... 25 82 5.2 Phase 2: MDR Selection ...................................... 25 83 5.3 Phase 3: Backup MDR Selection ............................... 27 84 5.4 Phase 4: Selection of the (Backup) MDR Parent ............... 27 85 5.5 Phase 5: Optional Selection of Non-Flooding MDRs ............ 28 86 6 Interface State Machine ..................................... 28 87 6.1 Interface states ............................................ 28 88 6.2 Events that cause interface state changes ................... 29 89 6.3 Changes to Interface State Machine .......................... 29 90 7 Adjacency Maintenance ....................................... 30 91 7.1 Changes to Neighbor State Machine ........................... 31 92 7.2 Whether to Become Adjacent .................................. 32 93 7.3 Whether to Eliminate an Adjacency ........................... 33 94 7.4 Sending Database Description Packets ........................ 33 95 7.5 Receiving Database Description Packets ...................... 33 96 8 Flooding Procedure .......................................... 34 97 8.1 LSA Forwarding Procedure .................................... 35 98 8.2 Sending Link State Acknowledgments .......................... 38 99 8.3 Retransmitting LSAs ......................................... 39 100 8.4 Receiving Link State Acknowledgments ........................ 39 101 9 Originating LSAs ............................................ 40 102 9.1 Routable Neighbors .......................................... 41 103 9.2 Partial and Full Topology LSAs .............................. 42 104 10 Calculating the Routing Table ............................... 44 105 11 Security Considerations ..................................... 45 106 12 IANA Considerations ......................................... 45 107 13 Acknowledgments ............................................. 45 108 14 Normative References ........................................ 45 109 15 Informative References ...................................... 46 110 A Packet Formats .............................................. 46 111 A.1 Options Field ............................................... 46 112 A.2 Link-Local Signaling ........................................ 46 113 A.3 Hello Packet DR and Backup DR Fields ........................ 51 114 A.4 LSA Formats and Examples .................................... 51 115 B Detailed Algorithms for MDR/BMDR Selection .................. 55 116 B.1 Detailed Algorithm for Step 2.4 (MDR Selection) ............. 55 117 B.2 Detailed Algorithm for Step 3.2 (BMDR Selection) ............ 56 118 C Min-Cost LSA Algorithm ...................................... 58 119 D Non-Ackable LSAs for Periodic Flooding ...................... 62 120 Authors Addresses ........................................... 62 121 Intellectual Property and Copyright Statements .............. 63 123 1. Introduction 125 This document specifies an extension of OSPF for IPv6 [RFC2328, 126 RFC2740], to support a new interface type for mobile ad hoc networks 127 (MANETs), i.e., for broadcast-capable, multihop wireless networks in 128 which routers and hosts can be mobile. This extension is also 129 applicable to non-mobile mesh networks using layer-3 routing. 130 Existing OSPF interface types do not perform adequately in such 131 environments, due to scaling issues regarding the flooding protocol 132 operation, inability of the Designated Router election protocol to 133 converge in all scenarios, and large numbers of adjacencies when 134 using a Point-to-Multipoint interface type. 136 An OSPF implementation that is extended with this MANET interface 137 type does not preclude the use of any existing interface types, and 138 is fully compatible with a legacy OSPF implementation. MANET 139 networks are represented externally as Point-to-Multipoint networks, 140 although the design borrows concepts used by the OSPF broadcast 141 interface type. 143 The approach taken is to generalize the concept of an OSPF Designated 144 Router (DR) and Backup DR to multihop wireless networks, in order to 145 reduce overhead by reducing the number of routers that must flood new 146 LSAs and reducing the number of adjacencies. The generalized 147 (Backup) Designated Routers are called (Backup) MANET Designated 148 Routers (MDRs). The MDRs form a connected dominating set (CDS), and 149 the MDRs and Backup MDRs together form a biconnected CDS for 150 robustness. By definition, each router in the MANET either belongs 151 to the CDS or is one hop away from it. A distributed algorithm is 152 used to select and dynamically maintain the biconnected CDS. 153 Adjacencies are established only between (Backup) MDRs and a subset 154 of their neighbors, thus resulting in a dramatic reduction in the 155 number of adjacencies in dense networks, compared to the approach of 156 forming adjacencies between all neighbor pairs. The OSPF extension 157 is called OSPF-MDR. 159 Hello packets are modified, using OSPF link-local signaling [LLS], 160 for two purposes: to provide neighbors with 2-hop neighbor 161 information that is required by the MDR selection algorithm, and to 162 allow differential Hellos that report only changes in neighbor 163 states. Differential Hellos can be sent more frequently without a 164 significant increase in overhead, in order to respond more quickly to 165 topology changes. 167 Each MANET router advertises a subset of its MANET neighbors as 168 point-to-point links in its router-LSA. The choice of which 169 neighbors to advertise is flexible, allowing overhead to be reduced 170 by advertising less topology information. Options are specified for 171 originating router-LSAs that provide full or partial topology 172 information. 174 This document is organized as follows. Section 2 presents an overview 175 of OSPF-MDR, Section 3 presents the new interface and neighbor data 176 items that are required for the extension, Section 4 describes the 177 Hello protocol, including procedures for maintaining the 2-hop 178 neighbor information, Section 5 describes the MDR selection 179 algorithm, Section 6 describes changes to the Interface state 180 machine, section 7 describes the procedures for forming adjacencies 181 and deciding which neighbors should become adjacent, Section 8 182 describes the flooding procedure, Section 9 specifies the 183 requirements and options for what to include in router-LSAs, and 184 Section 10 describes changes in the calculation of the routing table. 186 The appendix specifies packet formats, detailed algorithms for the 187 MDR selection algorithm, an algorithm for the selection of a subset 188 of neighbors to advertise in the router-LSA to provide shortest-path 189 routing, and a proposed option that uses "non-ackable" LSAs to 190 provide periodic flooding that reduces overhead in highly mobile 191 networks. 193 1.1. Terminology 195 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 196 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 197 document are to be interpreted as described in [RFC2119]. 199 In addition, this document uses the following terms: 201 MANET Interface 202 A new OSPF interface type that supports broadcast-capable, 203 multihop wireless networks. Two neighboring routers on a MANET 204 interface may not be able to communicate directly with each other. 205 A neighboring router on a MANET interface is called a MANET 206 neighbor. MANET neighbors are discovered dynamically using a 207 modification of OSPF's Hello protocol, which takes advantage of 208 the broadcast capability. 210 MANET Router 211 An OSPF router that has at least one MANET interface. 213 Differential Hello 214 A Hello packet that reduces the overhead of sending full Hellos, 215 by including only the Router IDs of neighbors whose state changed 216 recently. 218 2-Hop Neighbor Information 219 Information that specifies the bidirectional neighbors of each 220 neighbor. The modified Hello protocol provides each MANET router 221 with 2-hop neighbor information, which is used for selecting MDRs 222 and Backup MDRs. 224 MANET Designated Router (MDR) 225 One of a set of routers responsible for flooding new LSAs, and for 226 determining the set of adjacencies that must be formed. The set 227 of MDRs forms a connected dominating set and is a generalization 228 of the DR found in the broadcast network. 230 Backup MANET Designated Router (Backup MDR or BMDR) 231 One of a set of routers responsible for providing backup flooding 232 when neighboring MDRs fail, and for determining the set of 233 adjacencies that must be formed. The set of MDRs and Backup MDRs 234 forms a biconnected dominating set. The Backup MDR is a 235 generalization of the Backup DR found in the broadcast network. 237 MDR Other 238 A router is an MDR Other for a particular MANET interface if it is 239 neither an MDR nor a Backup MDR for that interface. 241 (Backup) MDR Parent 242 Each Backup MDR and MDR Other selects a Parent, which will be a 243 neighboring MDR if one exists. If the option of biconnected 244 adjacencies is chosen, then each MDR Other also selects a Backup 245 Parent, which will be a neighboring MDR/BMDR if one exists that is 246 not the Parent. Each router forms an adjacency with its Parent 247 and its Backup Parent (if it exists). 249 Bidirectional Neighbor 250 A neighboring router whose neighbor state is 2-Way or greater. 251 The set of such neighbors is called the Bidirectional Neighbor Set 252 (BNS). 254 Routable Neighbor 255 A bidirectional MANET neighbor becomes routable if its state is 256 Full, or if the SPF calculation has produced a route to the 257 neighbor and the neighbor satisfies a quality condition. Once a 258 neighbor becomes routable, it remains routable as long as it 259 remains bidirectional. Only routable MANET neighbors can be used 260 as next hops in the SPF calculation, and can be included in LSAs 261 originated by the router. 263 Non-flooding MDR 264 An MDR that does not immediately flood received LSAs back out the 265 receiving interface. Some MDRs may declare themselves non- 266 flooding in order to reduce flooding overhead. 268 2. Overview 270 This section provides an overview of OSPF-MDR, including motivation 271 and rationale for some of the design choices. 273 OSPF-MDR was motivated by the desire to extend OSPF to support 274 MANETs, while keeping the same design philosophy as OSPF and using 275 techniques that are similar to those of OSPF. For example, OSPF 276 reduces overhead in a broadcast network by electing a Designated 277 Router (DR) and Backup DR, and by having two neighboring routers form 278 an adjacency only if one of them is the DR or Backup DR. This idea 279 can be generalized to a multihop wireless network by forming a 280 spanning tree, with the edges of the tree being the adjacencies and 281 the interior (non-leaf) nodes of the tree being the generalized DRs, 282 called MANET Designated Routers (MDRs). 284 To provide better robustness and fast response to topology changes, 285 it was decided that a router should decide whether it is an MDR based 286 only on local information that can be obtained from neighbor's 287 Hellos. The resulting set of adjacencies therefore does not always 288 form a tree globally, but appears to be a tree locally. Similarly, 289 the Backup DR can be generalized to Backup MDRs (BMDRs), to provide 290 robustness through biconnected redundancy. The set of MDRs forms a 291 connected dominating set (CDS), and the set of MDRs and BMDRs forms a 292 biconnected dominating set. 294 The following subsections provide an overview of each of the main 295 features of OSPF-MDR, starting with a summary of how MDRs, BMDRs, and 296 adjacencies are selected. 298 2.1. Selection of MDRs, BMDRs, Parents, and Adjacencies 300 The MDR selection algorithm is distributed; each router selects 301 itself as an MDR, BMDR, or other router (called an "MDR Other") based 302 on information about its one-hop neighborhood, which is obtained from 303 Hello packets received from neighbors. Routers are ordered 304 lexicographically based on the tuple (RtrPri, MDR Level, RID), where 305 RtrPri is the Router Priority, MDR Level represents the current state 306 of the router (2 for an MDR, 1 for a BMDR, and 0 for an MDR Other), 307 and RID is the Router ID. Routers with lexicographically larger 308 values of (RtrPri, MDR Level, RID) are given preference for becoming 309 MDRs. 311 The MDR selection algorithm can be summarized as follows. If the 312 router itself has a larger value of (RtrPri, MDR Level, RID) than all 313 of its neighbors, it selects itself as an MDR. Otherwise, let Rmax 314 denote the neighbor with the largest value of (RtrPri, MDR Level, 315 RID). The router then selects itself as an MDR unless each neighbor 316 can be reached from Rmax in at most k hops via neighbors that have a 317 larger value of (RtrPri, MDR Level, RID) than the router itself, 318 where k is the parameter MDRConstraint, whose default value is 3. 319 This parameter serves to control the density of the MDR set, since 320 the MDR set need not be strictly minimal. 322 Similarly, a router that does not select itself as an MDR will select 323 itself as a BMDR unless each neighbor can be reached from Rmax via 324 two node-disjoint paths, using as intermediate hops only neighbors 325 that have a larger value of (RtrPri, MDR Level, RID) than the router 326 itself. 328 When a router selects itself as an MDR, it also decides which MDR 329 neighbors it should become adjacent with, to ensure that the set of 330 MDRs and the adjacencies between them form a connected backbone. 331 Each non-MDR router selects and becomes adjacent with an MDR neighbor 332 called its parent, thus ensuring that all routers are connected to 333 the MDR backbone. 335 If the option of biconnected adjacencies is chosen (AdjConnectivity = 336 2), then additional adjacencies are selected to ensure that the set 337 of MDRs and BMDRs, and the adjacencies between them, form a 338 biconnected backbone. In this case, each MDR Other selects and 339 becomes adjacent with an MDR/BMDR neighbor called its backup parent, 340 in addition to its MDR parent. 342 OSPF-MDR also provides the option of full-topology adjacencies 343 (AdjConnectivity = 0). If this option is selected, then each router 344 forms an adjacency with each bidirectional neighbor. 346 Prioritizing routers according to (RtrPri, MDR Level, RID) allows 347 neighboring routers to agree on which routers should become an MDR, 348 and gives higher priority to existing MDRs, which increases the 349 lifetime of MDRs and the adjacencies between them. In addition, 350 parents are selected to be existing adjacent neighbors whenever 351 possible, to avoid forming new adjacencies unless necessary. Once a 352 neighbor becomes adjacent, it remains adjacent as long as the 353 neighbor is bidirectional and either the neighbor or the router 354 itself is an MDR or BMDR (similar to OSPF). The above rules reduce 355 the rate at which new adjacencies are formed, which is important 356 since database exchange must be performed whenever a new adjacency is 357 formed. 359 2.2. Flooding Procedure 361 When an MDR receives a new LSA on a MANET interface, it immediately 362 floods the LSA back out the receiving interface unless it can be 363 determined that such flooding is unnecessary. When a Backup MDR 364 receives a new LSA on a MANET interface, it waits a short interval 365 (BackupWaitInterval), and then floods the LSA only if it has a 366 neighbor that did not flood or acknowledge the LSA and is not known 367 to be a neighbor of another neighbor (of the Backup MDR) that flooded 368 the LSA. 370 MDR Other routers never flood LSAs back out the receiving interface. 371 To exploit the broadcast nature of MANETs, a new LSA is processed 372 (and possibly forwarded) if it is received from any neighbor in state 373 2-Way or greater. The flooding procedure also avoids redundant 374 forwarding of LSAs when multiple interfaces exist. 376 2.3. Link State Acknowledgments 378 All Link State Acknowledgment packets are multicast. An LSA is 379 acknowledged if it is a new LSA, or if it is a duplicate LSA received 380 as a unicast. (A duplicate LSA received as multicast is not 381 acknowledged.) An LSA that is flooded back out the same interface is 382 treated as an implicit acknowledgment. Link state acknowledgments 383 may be delayed up to AckInterval seconds to allow coalescing multiple 384 acknowlegments in the same packet. The only exception is that 385 (Backup) MDRs send a multicast link state acknowledgment immediately 386 when a duplicate LSA is received as a unicast, in order to prevent 387 additional retransmissions. Only link state acknowledgments from 388 adjacent neighbors are processed, and retransmitted LSAs are sent 389 (via unicast) only to adjacent neighbors. 391 2.4. Routable Neighbors 393 In OSPF, a neighbor must typically be fully adjacent (in state Full) 394 for it to be used in the SPF calculation. An exception exists for an 395 OSPF broadcast network, to avoid requiring all pairs of routers in 396 such a network to form adjacencies, which would generate a large 397 amount of overhead. In such a network, a router can use a non- 398 adjacent neighbor as a next hop as long as both routers are fully 399 adjacent with the Designated Router. We define this neighbor 400 relationship as a "routable neighbor" and extend its usage to the 401 MANET interface type. All fully adjacent neighbors are routable, but 402 some neighbors for which a full adjacency does not exist may be 403 routable if other criteria are met. 405 A MANET neighbor becomes routable if its state is Full, or if it is 406 bidirectional and the SPF calculation has produced a route to the 407 neighbor. (A flexible quality condition may also be required.) Only 408 routable MANET neighbors can be used as next hops in the SPF 409 calculation, and can be included in the router-LSA originated by the 410 router. The idea is that if the SPF calculation has produced a route 411 to the neighbor, then it makes sense to take a "shortcut" and forward 412 packets directly to the neighbor. 414 The routability condition is a generalization of the way that 415 neighbors on broadcast networks are treated in the SPF calculation. 416 The network-LSA of an OSPF broadcast network implies that a router 417 can use a non-adjacent neighbor as a next hop. But a network-LSA 418 cannot describe the general topology of a MANET, making it necessary 419 to explicitly include non-adjacent neighbors in the router-LSA. 420 Allowing only adjacent neighbors in LSAs would either result in 421 suboptimal paths or would require a large number of adjacencies. 423 2.5. Partial and Full Topology LSAs 425 This specification allows routers to originate both full-topology 426 LSAs, which advertise links to all routable neighbors, and partial- 427 topology LSAs, which advertise only a subset of such links. In a 428 dense network, partial-topology LSAs are typically much smaller than 429 full-topology LSAs, thus achieving better scalability. 431 Each router advertises a subset of its routable neighbors as point- 432 to-point connections in its router-LSA. The choice of which 433 neighbors to advertise is flexible, and is determined by the 434 configurable parameter LSAFullness. As a minimum requirement, each 435 router must advertise a minimum set of "backbone" neighbors in its 436 router-LSA. This minimum choice corresponds to LSAFullness = 0. 437 This choice results in the minimum amount of LSA flooding overhead, 438 but does not provide routing along shortest paths. At the other 439 extreme, if LSAFullness = 4, then each router originates a full LSA, 440 which includes all routable neighbors. 442 Setting LSAFullness to 1 or 2 results in min-cost LSAs, which provide 443 routing along shortest (minimum-cost) paths. Each router decides 444 which neighbors to include in its router-LSA based on 2-hop neighbor 445 information obtained from its neighbors' Hellos. Each router 446 includes in its LSA the minimum set of neighbors necessary to provide 447 a shortest path between each pair of its neighbors. If LSAFullness = 448 2, then redundant paths are provided, to increase robustness and/or 449 allow multiple equal-cost routes to each destination. 451 Setting LSAFullness to 3 results in MDR full LSAs. Each (Backup) MDR 452 originates a full LSA that includes all routable neighbors, while 453 each MDR Other originates minimal LSAs. This choice does not provide 454 routing along shortest paths, but simulations have shown that it 455 provides routing along nearly shortest paths with relatively low 456 overhead. 458 The above LSA options are interoperable with each other, because they 459 all require the router-LSA to include a minimum set of neighbors, and 460 because the construction of the router-LSA (described in Section 461 9.2.3) ensures that the router-LSAs originated by different routers 462 are consistent. 464 2.6. Modified Hello Protocol 466 OSPF-MDR uses the same Hello format as OSPFv3, but appends additional 467 information to Hello packets using link-local signaling (LLS), in 468 order to indicate the set of bidirectional neighbors and other 469 information that is used by the MDR selection algorithm and the min- 470 cost LSA algorithm. In addition to full Hellos, which include the 471 same set of neighbor IDs as OSPFv3 Hellos, OSPF-MDR allows the use of 472 differential Hellos, which include only the IDs of neighbors whose 473 state (or other information) has recently changed (within the last 474 HelloRepeatCount Hellos). 476 Differential Hellos are sent every HelloInterval seconds, except when 477 full Hellos are sent, which happens once every 2HopRefresh Hellos. 478 The default value of 2HopRefresh is 1, i.e., the default is to send 479 only full Hellos. The default value for HelloInterval is 2 seconds. 480 Differential Hellos are used to reduce overhead and to allow Hellos 481 to be sent more frequently, for faster reaction to topology changes. 483 3. Interface and Neighbor Data Structures 485 3.1. Changes to Interface Data Structure 487 The following modified or new data items are required for the 488 Interface Data Structure of a MANET interface: 490 Type 491 A router that implements this extension can have one or more 492 interfaces of type MANET, in addition to the OSPF interface types 493 defined in RFC 2328. 495 State 496 The possible states for a MANET interface are the same as for a 497 broadcast interface. However, the DR and Backup states now imply 498 that the router is an MDR or Backup MDR, respectively. 500 MDR Level 501 The MDR Level is equal to MDR (value 2) if the router is an MDR, 502 Backup MDR (value 1) if the router is a Backup MDR, and MDR Other 503 (value 0) otherwise. The MDR Level is used by the MDR selection 504 algorithm. 506 MDR Parent 507 Each non-MDR router selects an MDR Parent, as described in Section 508 5.4. The MDR Parent will be a neighboring MDR, if one exists. 509 The MDR Parent is initialized to 0.0.0.0, indicating the lack of 510 an MDR Parent. A non-MDR router includes the Router ID of its MDR 511 Parent in the DR field of each Hello sent on the interface. 513 Backup MDR Parent 514 If the option of biconnected adjacencies is chosen, then each MDR 515 Other selects a Backup MDR Parent, as described in Section 5.4. 516 The Backup MDR Parent will be a neighboring MDR/BMDR, if one 517 exists that is not the MDR Parent. The Backup MDR Parent is 518 initialized to 0.0.0.0, indicating the lack of a Backup MDR 519 Parent. An MDR Other includes the Router ID of its Backup MDR 520 Parent in the Backup DR field of each Hello sent on the interface. 522 Router Priority 523 An 8-bit unsigned integer. A router with a larger Router Priority 524 is more likely to be selected as an MDR. The Router Priority for 525 a MANET interface can be changed dynamically based on any 526 criteria, including bandwidth capacity, willingness to be a relay 527 (which can depend on battery life, for example), number of 528 neighbors (degree), and neighbor stability. A router that has 529 been a (Backup) MDR for a certain amount of time can reduce its 530 Router Priority so that the burden of being a (Backup) MDR can be 531 shared among all routers. If the Router Priority for a MANET 532 interface is changed, then the interface variable 533 MDRNeighborChange must be set. 535 Hello Sequence Number (HSN) 536 The 16-bit sequence number carried by the Hello TLV. The HSN is 537 incremented by 1 every time a (differential or full) Hello is sent 538 on the interface. 540 MDRNeighborChange 541 A single-bit variable set to 1 if a neighbor change has occurred 542 that requires the MDR selection algorithm to be executed. 544 3.2. New Configurable Interface Parameters 546 The following new configurable interface parameters are required for 547 a MANET interface. The default values for HelloInterval, 548 RouterDeadInterval, and RxmtInterval for a MANET interface are 2, 6, 549 and 7 seconds, respectively. 551 The default configuration for OSPF-MDR uses uniconnected adjacencies 552 (AdjConnectivity = 1) and partial-topology LSAs that provide 553 shortest-path routing (LSAFullness = 1). This is the most scalable 554 configuration that provides shortest-path routing. Other 555 configurations may be preferable in special circumstances. For 556 example, setting LSAFullness to 4 provides full-topology LSAs, and 557 setting LSAFullness to 0 provides minimal LSAs that minimize overhead 558 but do not ensure shortest-path routing. Setting AdjConnectivity to 559 2 increases robustness by providing a biconnected adjacency subgraph, 560 and setting AdjConnectivity to 0 results in full-topology 561 adjacencies. 563 Although all routers should preferably choose the same values for the 564 new configurable interface parameters, this is not required. OSPF- 565 MDR was carefully designed so that correct interoperation is achieved 566 even if each router sets these parameters independently of the other 567 routers. 569 AdjConnectivity 570 If equal to the default value of 1, then the set of adjacencies 571 forms a (uni)connected graph. If equal to the optional value of 2, 572 then the set of adjacencies forms a biconnected graph. If 573 AdjConnectivity is 0, then adjacency reduction is not used, i.e., 574 the router becomes adjacent with all of its neighbors. 576 MDRConstraint 577 A parameter of the MDR selection algorithm, which affects the 578 number of MDRs selected. The default value of 3 results in nearly 579 the minimum number of MDRs. The optional value 2 results in a 580 larger number of MDRs. 582 BackupWaitInterval 583 The number of seconds that a Backup MDR must wait after receiving 584 a new LSA, before it decides whether to flood the LSA. Default 585 value is 0.5 second. 587 LSAFullness 588 Determines which neighbors a router should advertise in its 589 router-LSA. The value 0 results in minimal LSAs that include only 590 "backbone" neighbors. The values 1 and 2 result in partial- 591 topology LSAs that provide shortest-path routing, with value 2 592 providing redundant paths. The value 3 results in (Backup) MDRs 593 originating full LSAs and other routers originating minimal LSAs. 594 The value 4 results in all routers originating full LSAs. The 595 default value is 1. 597 AckInterval 598 The maximum number of seconds that an acknowledgment may be held 599 before it is multicast so that acknowledgments may be coalesced. 600 The default value is 2 seconds. 602 2HopRefresh 603 One out of every 2HopRefresh Hellos sent on the interface must be 604 a full Hello. All other Hellos are differential. The default 605 value is 1, i.e., the default is to send only full Hellos. If 606 differential Hellos are used, the recommended value of 2HopRefresh 607 is 3. 609 HelloRepeatCount 610 The number of consecutive Hellos in which a neighbor must be 611 included when its state changes, if differential Hellos are used. 612 This parameter must be set to 3. 614 3.3. Changes to Neighbor Data Structure 616 The neighbor states are the same as for OSPF. However, the data for 617 a MANET neighbor that has transitioned to the Down state must be 618 maintained for at least HelloInterval * HelloRepeatCount seconds, to 619 allow the state change to be reported in differential Hellos. The 620 following new data items are required for the Neighbor Data Structure 621 of a neighbor on a MANET interface. 623 Neighbor Hello Sequence Number (NHSN) 624 The Hello sequence number contained in the last Hello received 625 from the neighbor. 627 A-bit 628 The A-bit copied from the Hello TLV of the last Hello received 629 from the neighbor. This bit is 1 if the neighbor is not using 630 adjacency reduction. 632 FullHelloRcvd 633 A single-bit variable equal to 1 if a full Hello has been received 634 from the neighbor. 636 Neighbor's MDR Level 637 The MDR Level of the neighbor, based on the DR and Backup DR 638 fields of the last Hello packet received from the neighbor or from 639 the MDR TLV in a DD packet received from the neighbor. 641 Neighbor's MDR Parent 642 The neighbor's choice for MDR Parent, obtained from the DR field 643 of the last Hello packet received from the neighbor or from the 644 MDR TLV in a DD packet received from the neighbor. 646 Neighbor's Backup MDR Parent 647 The neighbor's choice for Backup MDR Parent, obtained from the 648 Backup DR field of the last Hello packet received from the 649 neighbor or from the MDR TLV in a DD packet received from the 650 neighbor. 652 Child 653 A single-bit variable equal to 1 if the neighbor is a child, i.e., 654 if the neighbor has selected the router as a (Backup) MDR Parent. 656 Dependent Neighbor 657 A single-bit variable equal to 1 if the neighbor is a Dependent 658 Neighbor, which is decided by the MDR selection algorithm. 659 Dependent Neighbors become adjacent. The set of all Dependent 660 Neighbors is called the Dependent Neighbor Set (DNS). 662 Dependent Selector 663 A single-bit variable equal to 1 if the neighbor has selected the 664 router to be Dependent. 666 Selected Advertised Neighbor (SAN) 667 A single-bit variable equal to 1 if the neighbor is a selected 668 advertised neighbor. The set of all Selected Advertised Neighbors 669 is called the Selected Advertised Neighbor Set (SANS). The SANS 670 consists of neighbors that the router has selected to be included 671 in the router-LSA, along with other neighbors that are required to 672 be included. 674 Routable 675 A single-bit variable equal to 1 if the neighbor is routable. A 676 neighbor is routable if either its state is Full, or the routing 677 table includes a route to the neighbor. Only routable neighbors 678 are included in the router-LSA and are allowed as next hops in the 679 routing table. 681 Neighbor's Bidirectional Neighbor Set (BNS) 682 The neighbor's set of bidirectional neighbors, which is updated 683 when a Hello is received from the neighbor. 685 Neighbor's Dependent Neighbor Set (DNS) 686 The neighbor's set of Dependent Neighbors, which is updated when a 687 Hello is received from the neighbor. 689 Neighbor's Selected Advertised Neighbor Set (SANS) 690 The neighbor's set of Selected Advertised Neighbors, which is 691 updated when a Hello is received from the neighbor. 693 Neighbor's Link Metrics 694 The link metric for each of the neighbor's bidirectional 695 neighbors, obtained from the Metric TLV appended to each Hello. 697 4. Hello Protocol 699 The MANET interface utilizes Hellos for neighbor discovery and for 700 enabling neighbors to learn 2-hop neighbor information. The protocol 701 is flexible because it allows the use of full or differential Hellos. 702 Full Hellos list all neighbors in state Init or above, as in OSPFv3, 703 whereas differential Hellos list only neighbors whose status as a 704 bidirectional neighbor, Dependent Neighbor, or Selected Advertised 705 Neighbor has recently changed. Differential Hellos are used to 706 reduce overhead, and they allow Hellos to be sent more frequently 707 (for faster reaction to topology changes). If differential Hellos 708 are used, full Hellos are sent less frequently to ensure that all 709 neighbors have current 2-hop neighbor information. 711 4.1. Sending Hello Packets 713 Hello packets are sent according to [RFC2740] Section 3.2.1.1 and 714 [RFC2328] Section 9.5 with the following MANET specific 715 specifications beginning after paragraph 3 of Section 9.5. The Hello 716 packet format is defined in [RFC2740] A.3.2, except for the ordering 717 of the Neighbor IDs and the meaning of the DR and Backup DR fields as 718 described below. 720 Similar to [RFC2328], the DR and Backup DR fields indicate whether 721 the router is an MDR or Backup MDR. If the router is an MDR, then 722 the DR field is the router's own Router ID, and if the router is a 723 Backup MDR, then the Backup DR field is the router's own Router ID. 724 These fields are also used to advertise the router's MDR Parent and 725 Backup MDR Parent, as specified in Section A.3 and Section 5.4. 727 Hellos are sent every HelloInterval seconds. Full Hellos are sent 728 every 2HopRefresh Hellos, and differential Hellos are sent at all 729 other times. For example, if 2HopRefresh is equal to 3, then every 730 third Hello is a full Hello. If 2HopRefresh is set to 1, then all 731 Hellos are full (the default). 733 The neighbor IDs included in the body of each Hello are divided into 734 the following five disjoint lists of neighbors (some of which may be 735 empty), and must appear in the following order: 737 List 1. Neighbors whose state recently changed to Down (included 738 only in differential Hellos). 739 List 2. Neighbors in state Init. 740 List 3. Dependent Neighbors. 742 List 4. Selected Advertised Neighbors. 743 List 5. Unselected bidirectional neighbors, defined as bidirectional 744 neighbors that are neither Dependent nor Selected Advertised 745 Neighbors. 747 Note that all neighbors in Lists 3 through 5 are bidirectional 748 neighbors. These lists are used to update the neighbor's 749 Bidirectional Neighbor Set (BNS), Dependent Neighbor Set (DNS), and 750 Selected Advertised Neighbor Set (SANS) when a Hello is received. 752 Note that the above five lists are disjoint, so each neighbor can 753 appear in at most one list. Also note that some or all of the five 754 lists can be empty. 756 Link-local signaling (LLS) is used to append up to two TLVs to each 757 MANET Hello packet. The format for LLS is given in Section A.2. The 758 Hello TLV is appended to each (full or differential) MANET Hello 759 packet. It indicates whether the Hello is full or differential, and 760 gives the Hello Sequence Number (HSN) and the number of neighbor IDs 761 in each of Lists 1 through 4 defined above. The size of List 5 is 762 then implied by the packet length field of the Hello. The format of 763 the Hello TLV is given in Section A.2.3. 765 In both full and differential Hellos, the appended Hello TLV is built 766 as follows. 768 o The Sequence Number field is set to the current HSN for the 769 interface; the HSN is then incremented. 771 o The D-bit of the Hello TLV is set to 1 for a differential Hello 772 and 0 for a full Hello. 774 o The A-bit of the Hello TLV is set to 1 if AdjConnectivity is 0 775 (the router is not using adjacency reduction); otherwise it is set 776 to 0. 778 o The N1, N2, N3, and N4 fields are set to the number of neighbor 779 IDs in the body of the Hello that are in List 1, List 2, List 3, 780 and List 4, respectively. (N1 is always zero in a full Hello.) 782 If LSAFullness is 1 or 2, a Metric TLV is appended to each MANET 783 Hello packet. It advertises link costs to neighbors, to allow the 784 selection of neighbors to include in partial-topology LSAs. The 785 format of the Metric TLV is given in Section A.2.5. The I bit of the 786 Metric TLV can be set to 0 or 1. If the I bit is set to 0, then the 787 Metric TLV does not contain neighbor IDs, and contains the metric for 788 each bidirectional neighbor listed in the (full or differential) 789 Hello, in the same order. If the I bit is set to 1, then the Metric 790 TLV includes the neighbor ID and metric for each bidirectional 791 neighbor listed in the Hello whose metric is not equal to the Default 792 Metric field of the TLV. 794 The I bit should be chosen to minimize the size of the Metric TLV. 795 This can be achieved by choosing the the I bit to be 1 if and only if 796 the number of bidirectional neighbors listed in the Hello whose 797 metric differs from the Default Metric field is less than 1/3 of the 798 total number of bidirectional neighbors listed in the Hello. 800 For example, if all neighbors have the same metric, then the I bit 801 should be set to 1, with the Default Metric equal to this metric, 802 avoiding the need to include neighbor IDs and corresponding metrics 803 in the TLV. At the other extreme, if all neighbors have different 804 metrics, then the I bit should be set to 0 to avoid listing the same 805 neighbor IDs in both the body of the Hello and the Metric TLV. 807 In both full and differential Hello packets, the L bit is set in the 808 Hello's option field to indicate LLS. 810 4.1.1. Full Hello Packet 812 In a full Hello, the neighbor ID list includes all neighbors in state 813 Init or higher, in the order described above. The Hello TLV is built 814 as described above, and if LSAFullness is 1 or 2, the Metric TLV is 815 built as specified in Section A.2.5. 817 4.1.2. Differential Hello Packet 819 In a differential Hello, the five neighbor ID lists defined in 820 Section 4.1 are populated as follows: 822 List 1 includes all neighbors in state Down that transitioned to this 823 state within the last HelloRepeatCount Hellos. 825 List 2 includes all neighbors in state Init that transitioned to this 826 state within the last HelloRepeatCount Hellos. 828 List 3 includes all Dependent Neighbors that became Dependent within 829 the last HelloRepeatCount Hellos. 831 List 4 includes all Selected Advertised Neighbors that became 832 Selected Advertised Neighbors within the last HelloRepeatCount 833 Hellos. 835 List 5 includes all unselected bidirectional neighbors (defined in 836 Section 4.1) that became unselected bidirectional neighbors within 837 the last HelloRepeatCount Hellos. 839 In addition, if a Metric TLV is appended to the Hello, then each 840 bidirectional neighbor whose link metric changed within the last 841 HelloRepeatCount Hellos must also be included in the body of the 842 Hello (in the appropriate list). 844 4.2. Receiving Hello Packets 846 A Hello packet received on a MANET interface is processed as 847 described in [RFC2740] Section 3.2.2.1 and the first two paragraphs 848 of [RFC2328] Section 10.5, followed by the processing specified 849 below. 851 The source of a received Hello packet is identified by the Router ID 852 found in the Hello's OSPF packet header. If a matching neighbor 853 cannot be found in the interface's data structure, one is created 854 with the Neighbor ID set to the Router ID found in the OSPF packet 855 header, the state initialized to Down, all MANET-specific neighbor 856 variables (specified in Section 3.3) initialized to zero, and the 857 neighbor's DNS, SANS, and BNS initialized to empty sets. 859 The neighbor structure's Router Priority is set to the value of the 860 corresponding field in the received Hello packet. The Neighbor's MDR 861 Parent is set to the value of the DR field, and the Neighbor's Backup 862 MDR Parent is set to the value of the Backup DR field. 864 Now the rest of the Hello Packet is examined, generating events to be 865 given to the neighbor and interface state machines. These state 866 machines are specified either to be executed or scheduled (see 867 [RFC2328] Section 4.4 "Tasking support"). For example, by specifying 868 below that the neighbor state machine be executed in line, several 869 neighbor state transitions may be affected by a single received 870 Hello. 872 o If the L bit in the options field is not set, then an error has 873 occurred and the Hello is discarded. 875 o If the LLS contains a Hello TLV, the neighbor state machine is 876 executed with the event HelloReceived. Otherwise, an error has 877 occurred and the Hello is discarded. 879 o The Hello Sequence Number and the A-bit in the Hello TLV are 880 copied to the neighbor's data structure. 882 o The DR and Backup DR fields are processed as follows. 884 (1) If the DR field is equal to the neighbor's Router ID, 885 set the neighbor's MDR Level to MDR. 887 (2) Else if the Backup DR field is equal to the neighbor's 888 Router ID, set the neighbor's MDR Level to Backup MDR. 890 (3) Else, set the neighbor's MDR Level to MDR Other. 892 (4) If the DR or Backup DR field is equal to the router's own 893 Router ID, the neighbor's Child variable is set to 1; 894 otherwise it is set to zero. 896 The neighbor ID list of the Hello is divided as follows into the five 897 lists defined in Section 4.1, where N1, N2, N3, and N4 are obtained 898 from the corresponding fields of the Hello TLV. List 1 is defined to 899 be the first N1 neighbor IDs, List 2 is defined to be the next N2 900 neighbor IDs, List 3 is defined to be the next N3 neighbor IDs, List 901 4 is defined to be the next N4 neighbor IDs, and List 5 is defined to 902 be the remaining neighbor IDs in the Hello. 904 Further processing of the Hello depends on whether it is full or 905 differential, which is indicated by the value of the D-bit of the 906 Hello TLV. 908 4.2.1. Full Hello Packet 910 If the received Hello is full (the D-bit of the Hello TLV is 0), the 911 following steps are performed: 913 o If the N1 field of the Hello TLV is not zero, then an error has 914 occurred and the Hello is discarded. Otherwise, set FullHelloRcvd 915 to 1. 917 o In the neighbor structure, modify the neighbor's DNS to equal the 918 set of neighbor IDs in the Hello's List 3, modify the neighbor's 919 SANS to equal the set of neighbor IDs in the Hello's List 4, and 920 modify the neighbor's BNS to equal the set of neighbor IDs in the 921 union of Lists 3, 4, and 5. 923 o If the router itself appears in the Hello's neighbor ID list, the 924 neighbor state machine is executed with the event 2-WayReceived 925 after the Hello is processed. Otherwise, the neighbor state 926 machine is executed with the event 1-WayReceived after the Hello 927 is processed. 929 4.2.2. Differential Hello Packet 931 If the received Hello is differential (the D-bit of the Hello TLV is 932 1), the following steps are performed: 934 (1) For each neighbor ID in List 1 or List 2 of the Hello: 936 o Remove the neighbor ID from the neighbor's DNS, SANS, 937 and BNS, if it belongs to the neighbor set. 939 (2) For each neighbor ID in List 3 of the Hello: 941 o Add the neighbor ID to the neighbor's DNS and BNS, if it 942 does not belong to the neighbor set. 944 o Remove the neighbor ID from the neighbor's SANS, if it 945 belongs to the neighbor set. 947 (3) For each neighbor ID in List 4 of the Hello: 949 o Add the neighbor ID to the neighbor's SANS and BNS, if it 950 does not belong to the neighbor set. 952 o Remove the neighbor ID from the neighbor's DNS, if it 953 belongs to the neighbor set. 955 (4) For each neighbor ID in List 5 of the Hello: 957 o Add the neighbor ID to the neighbor's BNS, if it does not 958 belong to the neighbor set. 960 o Remove the neighbor ID from the neighbor's DNS and SANS, if 961 it belongs to the neighbor set. 963 (5) If the router's own RID appears in List 1, execute the neighbor 964 state machine with the event 1-WayReceived after the Hello is 965 processed. 967 (6) If the router's own RID appears in List 2, 3, 4, or 5, execute 968 the neighbor state machine with the event 2-WayReceived after 969 the Hello is processed. 971 (7) If the router's own RID does not appear in the Hello's neighbor 972 ID list, and the neighbor state is 2-Way or greater, and the 973 Hello Sequence Number is less than or equal to the previous 974 sequence number plus HelloRepeatCount, then the neighbor state 975 machine is executed with the event 2-WayReceived after the Hello 976 is processed (the state does not change). 978 (8) If 2-WayReceived is not executed, then 1-WayReceived is executed 979 after the Hello is processed. 981 4.2.3. Additional Processing for Both Hello Types 983 The following applies to both full and differential Hellos. 985 If the router itself appears in the neighbor's DNS, the neighbor's 986 Dependent Selector variable is set to 1; otherwise it is set to 0. 988 The receiving interface's MDRNeighborChange variable is set to 1 if 989 any of the following changes occurred as a result of processing the 990 Hello: 992 o The neighbor's state changed from less than 2-Way to 2-Way or 993 greater, or vice versa. 995 o The neighbor is bidirectional and any of the following neighbor 996 variables has changed: MDR Level, Router Priority, FullHelloRcvd, 997 and Bidirected Neighbor Set (BNS). 999 The neighbor state machine is scheduled with the event AdjOK? if any 1000 of the following changes occurred as a result of processing the 1001 Hello: 1003 o The neighbor's state changed from less than 2-Way to 2-Way or 1004 greater. 1006 o The neighbor is bidirectional and its MDR Level has changed, or 1007 its Child variable or Dependent Selector variable has changed from 1008 0 to 1. 1010 If the LLS contains a Metric TLV, it is processed by updating the 1011 neighbor's link metrics according to the format of the Metric TLV 1012 specified in Section A.2.5. 1014 If LSAFullness is 1 or 2 (partial-topology LSAs), then the min-cost 1015 LSA algorithm (Appendix C) is executed and a new router-LSA is 1016 possibly originated as specified in Section 9.2.3 if any of the 1017 following changes occurred as a result of processing the Hello: 1019 o The neighbor's state changed from less than 2-Way to 2-Way or 1020 greater, or vice versa. 1022 o The neighbor is bidirectional and any of the following neighbor 1023 variables has changed: MDR Level, Router Priority, FullHelloRcvd, 1024 DNS, SANS, BNS, and MDR Parent(s). 1026 o Any of the neighbor's link metrics has changed as a result of 1027 processing the Metric TLV. 1029 4.3. Neighbor Acceptance Condition 1031 In wireless networks, a single Hello can be received from a neighbor 1032 with which a poor connection exists, e.g., because the neighbor is 1033 almost out of range. To avoid accepting poor quality neighbors, and 1034 to employ hysteresis, a router may require that a stricter condition 1035 be satisfied before changing the state of a MANET neighbor from Down 1036 to Init or greater. This condition is called the "neighbor 1037 acceptance condition", which by default is the reception of a single 1038 Hello or DD packet. For example, the neighbor acceptance condition 1039 may require that 2 consecutive Hellos be received from a neighbor 1040 before changing the neighbor's state from Down to Init. Other 1041 possible conditions include the reception of 3 consecutive Hellos, or 1042 the reception of 2 of the last 3 Hellos. The neighbor acceptance 1043 condition may also impose thresholds on other measurements such as 1044 received signal strength. 1046 The neighbor state transition for state Down and event HelloReceived 1047 is thus modified (see Section 7.1) to depend on the neighbor 1048 acceptance condition. 1050 5. MDR Selection Algorithm 1052 This section describes the MDR selection algorithm, which determines 1053 determines whether the router is an MDR, Backup MDR, or MDR Other on 1054 a given interface. The algorithm also selects the Dependent 1055 Neighbors and the (Backup) MDR Parent, which are used to decide which 1056 neighbors should become adjacent (see Section 7). 1058 The MDR selection algorithm is executed just before sending a Hello 1059 if the MDRNeighborChange bit is set for the interface; the bit is 1060 then cleared. To simplify the implementation, the MDR selection 1061 algorithm MAY be executed just before sending each Hello, to avoid 1062 having to determine when the MDRNeighborChange bit should be set. 1063 After running the MDR selection algorithm, the AdjOK? event may be 1064 invoked for some or all neighbors as specified in Section 7. 1066 The purpose of the MDRs is to provide a minimal set of relays for 1067 flooding LSAs, and the purpose of the Backup MDRs is to provide 1068 backup relays to flood LSAs when flooding by MDRs does not succeed. 1069 The set of MDRs forms a CDS, and the set of (Backup) MDRs forms a 1070 biconnected CDS. Note that there may be fewer Backup MDRs than MDRs, 1071 since the MDRs themselves may already provide some redundancy. 1073 Each MDR becomes adjacent with a subset of MDR neighbors called 1074 Dependent Neighbors, forming a connected backbone. Each non-MDR 1075 router connects to this backbone by selecting and becoming adjacent 1076 with an MDR neighbor called its MDR Parent. 1078 If AdjConnectivity = 2, then each (Backup) MDR becomes adjacent with 1079 additional (Backup) MDR neighbors to form a biconnected backbone, and 1080 each MDR Other selects and becomes adjacent with a second (Backup) 1081 MDR neighbor called its Backup MDR Parent, thus becoming connected to 1082 the backbone via two adjacencies. 1084 The MDR selection algorithm is a distributed CDS algorithm that uses 1085 2-hop neighbor information obtained from Hellos. More specifically, 1086 it uses as inputs the set of bidirectional neighbors (in state 2-Way 1087 or greater), the triplet (MDR Level, Router Priority, Router ID) for 1088 each such neighbor and for the router itself, and the neighbor 1089 variables Bidirectional Neighbor Set (BNS) and FullHelloRcvd for each 1090 such neighbor. The MDR selection algorithm can be implemented in 1091 O(d^2) time, where d is the number of neighbors. 1093 The above triplet will be abbreviated as (RtrPri, MDR Level, RID). 1094 The triplet (RtrPri, MDR Level, RID) is said to be larger for Router 1095 A than for Router B if the triplet for Router A is lexicographically 1096 greater than the triplet for Router B. Routers that have larger 1097 values of this triplet are preferred for selection as an MDR. The 1098 algorithm therefore prefers routers that are already MDRs, resulting 1099 in a longer average MDR lifetime. 1101 The MDR selection algorithm consists of five phases, the last of 1102 which is optional. Phase 1 creates the neighbor connectivity matrix, 1103 which determines which pairs of neighbors are neighbors of each 1104 other. Phase 2 decides whether the calculating router is an MDR, and 1105 which MDR neighbors are Dependent. Phase 3 decides whether the 1106 calculating router is a Backup MDR and, if AdjConnectivity = 2, which 1107 additional MDR/BMDR neighbors are Dependent. Phase 4 selects the MDR 1108 Parent and Backup MDR Parent. 1110 The algorithm simplifies considerably if AdjConnectivity is 0 (full- 1111 topology adjacencies). In this case, Phase 4 (parent selection) is 1112 not executed, and the set of Dependent Neighbors is empty. Also, 1113 Phase 3 (BMDR selection) is not required if AdjConnectivity is 0 or 1114 1. However, Phase 3 MUST be executed if AdjConnectivity is 2, and 1115 SHOULD be executed if AdjConnectivity is 0 or 1, since BMDRs improve 1116 robustness by providing backup flooding. 1118 A router that has selected itself as an MDR in Phase 2 MAY execute 1119 Phase 5 to possibly declare itself a non-flooding MDR. A non- 1120 flooding MDR is the same as a flooding MDR except that it does not 1121 immediately flood received LSAs back out the receiving interface, 1122 because it has determined that neighboring MDRs exist that will 1123 ensure all neighbors are covered. Instead, a non-flooding MDR 1124 performs backup flooding just like a BMDR. A non-flooding MDR 1125 maintains its MDR level (rather than being demoted to a BMDR) in 1126 order to maximize the stability of adjacencies. (The decision to 1127 form an adjacency does not depend on whether an MDR is non-flooding.) 1128 By having MDRs declare themselves to be non-flooding when possible, 1129 flooding overhead is reduced. The resulting overhead reduction can 1130 be dramatic for certain regular topologies, but has been found to be 1131 about 15% for random topologies. 1133 For convenience, in the following description, the term "bi-neighbor" 1134 will be used as an abbreviation for "bidirectional neighbor". 1136 5.1. Phase 1: Creating the Neighbor Connectivity Matrix 1138 The neighbor connectivity matrix (NCM) assigns a value of 0 or 1 for 1139 each pair of bi-neighbors, depending on the Bidirectional Neighbor 1140 Set (BNS) and the value of FullHelloRcvd for each neighbor. NCM is a 1141 symmetric matrix that defines a topology graph for the set of bi- 1142 neighbors. A value of 1 for a given pair of neighbors indicates that 1143 the neighbors are assumed to be bi-neighbors of each other in the MDR 1144 selection algorithm. Letting i denote the router itself, NCM(i,j) 1145 and NCM(j,i) are set to 1 for each bi-neighbor j. The value of the 1146 matrix is set as follows for each pair of bi-neighbors j and k. 1148 (1.1) If FullHelloRcvd is 1 for both neighbors j and k: NCM(j,k) = 1149 NCM(k,j) is 1 only if j belongs to the BNS of neighbor k and k 1150 belongs to the BNS of neighbor j. 1152 (1.2) If FullHelloRcvd is 1 for neighbor j and is 0 for neighbor k: 1153 NCM(j,k) = NCM(k,j) is 1 only if k belongs to the BNS of 1154 neighbor j. 1156 (1.3) If FullHelloRcvd is 0 for both neighbors j and k: NCM(j,k) = 1157 NCM(k,j) = 0. 1159 In step 1.1 above, two neighbors are considered to be bi-neighbors of 1160 each other only if they both agree that the other router is a bi- 1161 neighbor. This provides faster response to the failure of a link 1162 between two neighbors, since it is likely that one router will detect 1163 the failure before the other router. In step 1.2 above, only neighbor 1164 j has reported its full BNS, so neighbor j is believed in deciding 1165 whether j and k are bi-neighbors of each other. As Step 1.3 1166 indicates, two neighbors are assumed not to be bi-neighbors of each 1167 other if neither neighbor has reported its full BNS. 1169 5.2. Phase 2: MDR Selection 1171 Phase 2 depends on the parameter MDRConstraint, which affects the 1172 number of MDRs selected. The default value of 3 results in nearly the 1173 minimum number of MDRs, while the value 2 results in a larger number 1174 of MDRs. If AdjConnectivity = 0 (full-topology adjacencies), then 1175 the following steps are modified in that Dependent Neighbors are not 1176 selected. 1178 (2.1) The set of Dependent Neighbors is initialized to be empty. 1180 (2.2) If the router has a larger value of (RtrPri, MDR Level, RID) 1181 than all of its bi-neighbors, the router selects itself as an 1182 MDR, selects all of its MDR bi-neighbors as Dependent 1183 Neighbors, and if AdjConnectivity = 2, selects all of its BMDR 1184 bi-neighbors as Dependent Neighbors. Else, proceed to Step 1185 2.3. 1187 (2.3) Let Rmax be the bi-neighbor with the largest value of (RtrPri, 1188 MDR Level, RID). 1190 (2.4) Using NCM to determine the connectivity of bi-neighbors, 1191 compute the minimum number of hops, denoted hops(u), from Rmax 1192 to each other bi-neighbor u, using only intermediate nodes that 1193 are bi-neighbors with a larger value of (RtrPri, MDR Level, 1194 RID) than the router itself. If no such path from Rmax to u 1195 exists, then hops(u) equals infinity. (See Appendix B for a 1196 detailed algorithm using breadth-first search.) 1198 (2.5) If hops(u) is at most MDRConstraint for each bi-neighbor u, the 1199 router selects no Dependent Neighbors, and sets its MDR Level 1200 as follows: If the MDR Level is currently MDR, then it is 1201 changed to BMDR if Phase 3 will be executed and to MDR Other if 1202 Phase 3 will not be executed. Otherwise, the MDR Level is not 1203 changed. 1205 (2.6) Else, the router sets its MDR Level to MDR and selects the 1206 following neighbors as Dependent Neighbors: Rmax, each MDR bi- 1207 neighbor u such that hops(u) is greater than MDRConstraint, and 1208 if AdjConnectivity = 2, each BMDR bi-neighbor u such that 1209 hops(u) is greater than MDRConstraint. 1211 (2.7) If steps 2.1 through 2.6 resulted in the MDR Level changing to 1212 BMDR, or to MDR with AdjConnectivity equal to 1 or 2, then 1213 execute steps 2.1 through 2.6 again. (This is necessary 1214 because the change in MDR Level can cause the set of Dependent 1215 Neighbors and the BFS tree to change.) 1217 Step 2.4 can be implemented using a breadth-first search (BFS) 1218 algorithm to compute min-hop paths from node Rmax to all other bi- 1219 neighbors, modified to allow a node as an intermediate node only if 1220 its value of (RtrPri, MDR Level, RID) is larger than that of the 1221 router itself. A detailed description of this algorithm, which runs 1222 in O(d^2) time, is given in Appendix B. 1224 5.3. Phase 3: Backup MDR Selection 1226 (3.1) If the MDR Level is MDR (after running Phase 2) and 1227 AdjConnectivity is not 2, then proceed to Phase 4. (If the MDR 1228 Level is MDR and AdjConnectivity = 2, then Phase 3 may select 1229 additional Dependent Neighbors to create a biconnected 1230 backbone.) 1232 (3.2) Using NCM to determine the connectivity of bi-neighbors, 1233 determine whether or not there exist two node-disjoint paths 1234 from Rmax to each other bi-neighbor u, using only intermediate 1235 nodes that are bi-neighbors with a larger value of (RtrPri, MDR 1236 Level, RID) than the router itself. (See Appendix B for a 1237 detailed algorithm.) 1239 (3.3) If there exist two such node-disjoint paths from Rmax to each 1240 other bi-neighbor u, then the router selects no additional 1241 Dependent Neighbors and sets its MDR Level to MDR Other. 1243 (3.4) Else, the router sets its MDR Level to Backup MDR unless it 1244 already selected itself as an MDR in Phase 2, and if 1245 AdjConnectivity = 2, adds each of the following neighbors to 1246 the set of Dependent Neighbors: Rmax, and each MDR/BMDR bi- 1247 neighbor u such that step 3.2 did not find two node-disjoint 1248 paths from Rmax to u. 1250 (3.5) If steps 3.1 through 3.4 resulted in the MDR Level changing 1251 from MDR Other to BMDR, then run Phases 2 and 3 again. (This 1252 is necessary because running Phase 2 again can cause the MDR 1253 Level to change to MDR.) 1255 Step 3.2 can be implemented in O(d^2) time using the algorithm given 1256 in Appendix B. A simpler approximate algorithm is also given, which 1257 results in a larger number of BMDRs. 1259 5.4. Phase 4: Selection of the (Backup) MDR Parent 1261 Each BMDR and MDR Other selects (for each MANET interface) a Parent, 1262 which will be a neighboring MDR if one exists. If AdjConnectivity = 1263 2, then each MDR Other also selects a Backup Parent, which will be a 1264 neighboring MDR/BMDR if one exists that is not the Parent. Each 1265 router forms an adjacency with its Parent and its Backup Parent (if 1266 it exists). 1268 For a given MANET interface, let Rmax denote the router with the 1269 largest value of (RtrPri, MDR Level, RID) among all bidirectional 1270 neighbors, if such a neighbor exists that has a larger value of 1271 (RtrPri, MDR Level, RID) than the router itself. Otherwise, Rmax is 1272 null. 1274 If the calculating router has selected itself as an MDR, then the 1275 Parent is equal to the router itself, and the Backup Parent is Rmax. 1276 If the router has selected itself as a BMDR, then the Backup Parent 1277 is equal to the router itself. 1279 If the router is a BMDR or MDR Other, the Parent is selected to be 1280 any adjacent neighbor that is an MDR, if such a neighbor exists. If 1281 no adjacent MDR neighbor exists, then the Parent is selected to be 1282 Rmax. (By giving preference to neighbors that are already adjacent, 1283 the formation of a new adjacency is avoided when possible.) 1285 If AdjConnectivity = 2 and the calculating router is an MDR Other, 1286 then the Backup Parent is selected to be any adjacent neighbor that 1287 is an MDR or BMDR, other than the selected Parent, if such a neighbor 1288 exists. If no such neighbor exists, then the Backup Parent is 1289 selected to be the bidirectional neighbor, excluding the selected 1290 Parent, with the largest value of (RtrPri, MDR Level, RID). 1292 5.5. Phase 5: Optional Selection of Non-Flooding MDRs 1294 A router that has selected itself as an MDR MAY execute the following 1295 steps to possibly declare itself a non-flooding MDR. An MDR that 1296 does not execute the following steps is by default a flooding MDR. 1298 (5.1) If the router has a larger value of (RtrPri, MDR Level, RID) 1299 than all of its bi-neighbors, the router is a flooding MDR. Else, 1300 proceed to Step 5.2. 1302 (5.2) Let Rmax be the bi-neighbor that has the largest value of 1303 (RtrPri, MDR Level, RID). 1305 (5.3) Using NCM to determine the connectivity of bi-neighbors, 1306 compute the minimum number of hops, denoted hops(u), from Rmax to 1307 each other bi-neighbor u, using only intermediate nodes that are MDR 1308 bi-neighbors with a smaller value of (RtrPri, RID) than the router 1309 itself. (This can be done using BFS as in Step 2.4). 1311 (5.4) If hops(u) is at most MDRConstraint for each bi-neighbor u, 1312 then the router is a non-flooding MDR. Else, it is a flooding MDR. 1314 6. Interface State Machine 1316 6.1. Interface states 1318 No new states are defined for a MANET interface. However, the DR and 1319 Backup states now imply that the router is an MDR or Backup MDR, 1320 respectively. The following modified definitions apply to MANET 1321 interfaces: 1323 Waiting 1324 In this state, the router learns neighbor information from the 1325 Hello packets it receives, but is not allowed to run the MDR 1326 selection algorithm until it transitions out of the Waiting state 1327 (when the Wait Timer expires). This prevents unnecessary changes 1328 in the MDR selection resulting from incomplete neighbor 1329 information. The length of the Wait Timer is 2HopRefresh * 1330 HelloInterval seconds (the interval between full Hellos). 1332 DR Other 1333 The router has run the MDR selection algorithm and determined that 1334 it is not an MDR or a Backup MDR. 1336 Backup 1337 The router has selected itself as a Backup MDR. 1339 DR 1340 The router has selected itself as an MDR. 1342 6.2. Events that cause interface state changes 1344 All interface events defined in RFC 2328, Section 9.2 apply to MANET 1345 interfaces, except for BackupSeen and NeighborChange. BackupSeen is 1346 never invoked for a MANET interface (since seeing a Backup MDR does 1347 not imply that the router itself cannot also be an MDR or Backup 1348 MDR). 1350 The event NeighborChange is replaced with the new interface variable 1351 MDRNeighborChange, which indicates that the MDR selection algorithm 1352 must be executed due to a change in neighbor information (see Section 1353 4.2.3). 1355 6.3. Changes to Interface State Machine 1357 This section describes the changes to the interface state machine for 1358 a MANET interface. The two state transitions specified below are for 1359 state-event pairs that are described in RFC 2328, but have modified 1360 action descriptions because MDRs are selected instead of DRs. The 1361 state transition in RFC 2328 for the event NeighborChange is omitted; 1362 instead the new interface variable MDRNeighborChange is used to 1363 indicate when the MDR selection algorithm needs to be executed. The 1364 state transition for the event BackupSeen does not apply to MANET 1365 interfaces, since this event is never invoked for a MANET interface. 1366 The interface state transitions for the events Loopback and UnloopInd 1367 are unchanged from RFC 2328. 1369 State: Down 1370 Event: InterfaceUp 1371 New state: Depends on action routine. 1373 Action: Start the interval Hello Timer, enabling the periodic 1374 sending of Hello packets out the interface. If the router 1375 is not eligible to become an MDR (Router Priority is 0), 1376 the state transitions to DR Other. Otherwise, the state 1377 transitions to Waiting and the single shot Wait Timer is 1378 started. 1380 State: Waiting 1381 Event: WaitTimer 1382 New state: Depends on action routine. 1384 Action: Run the MDR selection algorithm, which may result in a 1385 change to the router's MDR Level, Dependent Neighbors, 1386 and (Backup) MDR Parent. As a result of this calculation, 1387 the new interface state will be DR Other, Backup, or DR. 1388 As a result of these changes, the AdjOK? neighbor event 1389 may be invoked for some or all neighbors. (See 1390 Section 7.) 1392 7. Adjacency Maintenance 1394 Adjacency forming and eliminating on non-MANET interfaces remain 1395 unchanged. Adjacency maintenance on a MANET interface requires 1396 changes to transitions in the neighbor state machine ([RFC2328] 1397 Section 10.3), to deciding whether to become adjacent ([RFC2328] 1398 Section 10.4), sending of DD packets ([RFC2328] Section 10.8), and 1399 receiving of DD packets ([RFC2328] Section 10.6). The specification 1400 below relates to the MANET interface only. 1402 Adjacencies are established with some subset of the router's 1403 neighbors. Each (Backup) MDR forms adjacencies with a subset of its 1404 (Backup) MDR neighbors to form a biconnected backbone, and each MDR 1405 Other forms adjacencies with two selected (Backup) MDR neighbors 1406 called "parents", thus providing a biconnected subgraph of 1407 adjacencies. 1409 An adjacency maintenance decision is made when any of the following 1410 four events occur between a router and its neighbor. The decision is 1411 made by executing the neighbor event AdjOK?. 1413 (1) The neighbor state changes from Init to 2-Way. 1414 (2) The MDR Level changes for the neighbor or for the router itself. 1415 (3) The neighbor is selected to be the (Backup) MDR Parent. 1416 (4) The neighbor selects the router to be its (Backup) MDR Parent. 1418 7.1. Changes to Neighbor State Machine 1420 The following specifies new transitions in the neighbor state 1421 machine. 1423 State(s): Down 1424 Event: HelloReceived 1425 New state: Depends on action routine. 1427 Action: If the neighbor acceptance condition is satisfied (see 1428 Section 4.3), the neighbor state transitions to Init and 1429 the Inactivity Timer is started. Otherwise, the neighbor 1430 remains in the Down state. 1432 State(s): Init 1433 Event: 2-WayReceived 1434 New state: 2-Way 1436 Action: Transition to neighbor state 2-Way. 1438 State(s): 2-Way 1439 Event: AdjOK? 1440 New state: Depends on action routine. 1442 Action: Determine whether an adjacency should be formed with the 1443 neighboring router (see Section 7.2). If not, the 1444 neighbor state remains at 2-Way and no further action is 1445 taken. 1447 Otherwise, the neighbor state changes to ExStart, and the 1448 following actions are performed. If the neighbor has a 1449 larger Router ID than the router's own ID, and the 1450 received packet is a DD packet with the initialize (I), 1451 more (M), and master (MS) bits set, then execute the 1452 event NegotiationDone, which causes the state to 1453 transition to Exchange. 1455 Otherwise (negotiation is not complete), the router 1456 increments the DD sequence number in the neighbor data 1457 structure. If this is the first time that an adjacency 1458 has been attempted, the DD sequence number should be 1459 assigned a unique value (like the time of day clock). It 1460 then declares itself master (sets the master/slave bit to 1461 master), and starts sending Database Description Packets, 1462 with the initialize (I), more (M) and master (MS) bits 1463 set, the MDR TLV included in an LLS, and the L bit set. 1464 This Database Description Packet should be otherwise 1465 empty. This Database Description Packet should be 1466 retransmitted at intervals of RxmtInterval until the next 1467 state is entered (see [RFC2328] Section 10.8). 1469 State(s): ExStart or greater 1470 Event: AdjOK? 1471 New state: Depends on action routine. 1473 Action: Determine whether the neighboring router should still be 1474 adjacent (see Section 7.3). If yes, there is no state 1475 change and no further action is necessary. Otherwise, 1476 the (possibly partially formed) adjacency must be 1477 destroyed. The neighbor state transitions to 2-Way. The 1478 Link state retransmission list, Database summary list, 1479 and Link state request list are cleared of LSAs. 1481 7.2. Whether to Become Adjacent 1483 The following defines the method to determine if an adjacency should 1484 be formed between neighbors in state 2-Way. The following procedure 1485 does not depend on whether AdjConnectivity is 1 or 2, but the 1486 selection of Dependent Neighbors (by the MDR selection algorithm) 1487 depends on AdjConnectivity. 1489 If adjacency reduction is not used (AdjConnectivity is 0), then an 1490 adjacency is formed with each neighbor in state 2-Way. Otherwise an 1491 adjacency is formed with a neighbor in state 2-Way if any of the 1492 following conditions is true: 1494 (1) The router is a (Backup) MDR and the neighbor is a (Backup) 1495 MDR and is either a Dependent Neighbor or a Dependent Selector. 1497 (2) The router is a (Backup) MDR and the neighbor is a child. 1499 (3) The neighbor is a (Backup) MDR and is the router's (Backup) 1500 Parent. 1502 (4) The neighbor is not using adjacency reduction, as indicated 1503 by the A-bit of the Hello TLV appended to the last Hello 1504 received from the neighbor. 1506 Otherwise, an adjacency is not established and the neighbor remains 1507 in state 2-Way. 1509 7.3. Whether to Eliminate an Adjacency 1511 The following defines the method to determine if an adjacency should 1512 be eliminated between neighbors in a state greater than 2-way. An 1513 adjacency is maintained if one of the following is true. 1515 (1) The router is an MDR. 1516 (2) The router is a Backup MDR. 1517 (3) The neighbor is an MDR. 1518 (4) The neighbor is a Backup MDR. 1520 Otherwise, the adjacency MAY be eliminated. 1522 7.4 Sending Database Description Packets 1524 Sending a DD packet on a MANET interface is the same as [RFC2740] 1525 Section 3.2.1.2 and [RFC2328] Section 10.8 with the following 1526 additions to paragraph 3 of Section 10.8. 1528 If the neighbor state is ExStart, the standard initialization packet 1529 is sent with an MDR TLV appended using LLS, and the L bit is set in 1530 the DD packet's option field. The DR and Backup DR fields of the MDR 1531 TLV are set exactly the same as the DR and Backup DR fields of a 1532 Hello sent on the same interface, as specified in Section A.3. 1534 7.5. Receiving Database Description Packets 1536 Processing a DD packet received on a MANET interface is the same as 1537 [RFC2328] Section 10.6, except for the changes described in this 1538 section. The following additional steps are performed before 1539 processing the packet based on neighbor state in paragraph 3 of 1540 Section 10.6. 1542 o If the DD packet's L bit is set in the options field and an MDR 1543 TLV is appended, then the MDR TLV is processed as follows. 1545 (1) If the DR field is equal to the neighhor's Router ID, 1546 (a) Set the MDR Level of the neighbor to MDR. 1547 (b) Set the neighbor's Dependent Selector variable to 1. 1549 (2) Else if the Backup DR field is equal to the neighbor's 1550 Router ID, 1551 (a) Set the MDR Level of the neighbor to Backup MDR. 1552 (b) Set the neighbor's Dependent Selector variable to 1. 1554 (3) Else, 1555 (a) Set the MDR Level of the neighbor to MDR Other. 1556 (b) Set the neighbor's Dependent Selector variable to 0. 1558 (4) If the DR or Backup DR field is equal to the router's own 1559 Router ID, the neighbor's Child variable is set to 1, 1560 otherwise it is zero. 1562 o If the neighbor state is Init, the neighbor event 2-WayReceived is 1563 executed. 1565 o If the MDR Level of the neighbor changed, the neighbor state 1566 machine is scheduled with the event AdjOK?. 1568 o If the neighbor's Child status has changed from 0 to 1, the 1569 neighbor state machine is scheduled with the event AdjOK?. 1571 o If the neighbor's neighbor state changed from less than 2-Way to 1572 2-Way or greater, the neighbor state machine is scheduled with the 1573 event AdjOK?. 1575 In addition, if the router accepts a received DD packet and processes 1576 its contents, then the following action SHOULD be performed for each 1577 LSA listed in the DD packet (whether the router is master or slave). 1578 If the router has an instance of the LSA in the Database summary list 1579 for the neighbor, which is the same or less recent than the LSA 1580 listed in the packet, then the LSA is removed from the Database 1581 summary list. This avoids including the LSA in a DD packet sent to 1582 the neighbor, when the neighbor already has an instance of the LSA 1583 that is the same or more recent. This optimization reduces overhead 1584 due to DD packets by approximately 50% in large networks. 1586 8. Flooding Procedure 1588 This section specifies the changes to RFC 2328, Section 13 for 1589 routers that support OSPF-MDR. The first part of Section 13 (before 1590 Section 13.1) is the same except for the following three changes. 1592 o To exploit the broadcast nature of MANETs, if the Link State 1593 Update (LSU) packet was received on a MANET interface, then the 1594 packet is dropped without further processing only if the sending 1595 neighbor is in a lesser state than 2-Way. Otherwise, the LSU 1596 packet is processed as described in this section. 1598 o If the received LSA is the same instance as the database copy, the 1599 following actions are performed in addition to step 7. For each 1600 MANET interface for which a BackupWait Neighbor Set exists for the 1601 LSA (see Section 8.1): 1603 (a) Remove the sending neighbor from the BackupWait Neighbor list 1604 if it belongs to the list. 1605 (b) For each neighbor on the receiving interface that belongs 1606 to the BNS for the sending neighbor, remove the neighbor 1607 from the BackupWait Neighbor list if it belongs to the list. 1609 o Step 8, which handles the case in which the database copy of the 1610 LSA is more recent than the received LSA, is modified as follows. 1611 If the sending neighbor is in a lesser state than Exchange, then 1612 the router does not send the LSA back to the sending neighbor. 1614 There are no changes to Sections 13.1, 13.2, or 13.4. The following 1615 subsections describe the changes to Sections 13.3 (Next step in the 1616 flooding procedure), 13.5 (Sending Link State Acknowledgments), 13.6 1617 (Retransmitting LSAs), and 13.7 (Receiving Link State 1618 Acknowledgments) of RFC 2328. 1620 8.1. LSA Forwarding Procedure 1622 Step 1 of [RFC2328], Section 13.3 should be performed, with the 1623 following change, so that the new LSA is placed on the Link State 1624 retransmission list for each appropriate adjacent neighbor. Step 1625 1(c) is replaced with the following action, so that the LSA is not 1626 placed on the retransmission list for a neighbor that has already 1627 acknowledged the LSA. 1629 o If the new LSA was received from this neighbor, or a link state 1630 acknowledgment (LS Ack) for the new LSA has already been received 1631 from this neighbor, examine the next neighbor. 1633 To determine whether an Ack for the new LSA has been received from 1634 the neighbor, the router maintains an Acked LSA List for each 1635 adjacent neighbor, as described in Section 8.4. When a new LSA is 1636 received, the Acked LSA List for each neighbor, on each MANET 1637 interface, should be updated by removing any LS Ack that is for an 1638 older instance of the LSA than the one received. 1640 The following description will use the notion of a "covered" 1641 neighbor. A neighbor k is defined to be covered if the LSA was sent 1642 as a multicast by a MANET neighbor j, and neighbor k belongs to the 1643 Bidirectional Neighbor Set (BNS) for neighbor j. A neighbor k is 1644 also defined to be covered if the LSA was sent to the multicast 1645 address AllSPFRouters by a neighbor j on a broadcast interface on 1646 which both j and k are neighbors. (Note that j must be the DR or 1647 Backup DR for the broadcast network, since only these routers may 1648 send LSAs to AllSPFRouters on a broadcast network.) 1649 Steps 2 through 5 of [RFC2328], Section 13.3 are unchanged if the 1650 outgoing interface (on which the LSA may be forwarded) is not of type 1651 MANET. If the outgoing interface is of type MANET, then steps 2 1652 through 5 are replaced with the following steps, to determine whether 1653 the LSA should be forwarded on each eligible MANET interface. 1655 (2) If either of the following two conditions is satisfied for every 1656 bidirectional neighbor on the interface, examine the next 1657 interface (the LSA is not flooded out this interface). 1659 (a) The LSA or an Ack for the LSA has been received from the 1660 neighbor (over any interface). 1662 (b) The LSA was received on a MANET or broadcast interface, and 1663 the neighbor is covered (defined above). 1665 Note that the above two conditions do not assume the outgoing 1666 interface is the same as the receiving interface. 1668 (3) If the LSA was received on this interface, and the router is an 1669 MDR Other for this interface, examine the next interface (the LSA 1670 is not flooded out this interface). 1672 (4) If the LSA was received on this interface, and the router is a 1673 Backup MDR or a non-flooding MDR for this interface, then the 1674 router waits BackupWaitInterval before deciding whether to flood 1675 the LSA. To accomplish this, the router creates a BackupWait 1676 Neighbor List for the LSA, which initially includes every 1677 bidirectional neighbor on this interface that fails to satisfy 1678 both conditions (a) and (b) in step 2. A single shot BackupWait 1679 Timer associated with the LSA is started, which is set to expire 1680 after BackupWaitInterval seconds plus a small amount of random 1681 jitter. (The actions performed when the BackupWait Timer expires 1682 are described below in Section 8.1.2.) Examine the next 1683 interface (the LSA is not immediately flooded out this 1684 interface). 1686 (5) If the router is a flooding MDR for this interface, or if the LSA 1687 was originated by the router itself, then the LSA is flooded out 1688 the interface (whether or not the LSA was received on this 1689 interface). The LSA is included in an LSU packet which is 1690 multicast out the interface using the destination IP address 1691 AllSPFRouters. 1693 (6) If the LSA was received on a MANET or broadcast interface that is 1694 different from this (outgoing) interface, then the following two 1695 steps SHOULD be performed to avoid redundant flooding. 1697 (a) If the router has a larger value of (RtrPri, MDR Level, RID) 1698 on the outgoing interface than every covered neighbor 1699 (defined above) that is a neighbor on BOTH the receiving and 1700 outgoing interfaces (or if no such neighbor exists), then the 1701 LSA is flooded out the interface. 1703 (b) Else, the router waits BackupWaitInterval before deciding 1704 whether to flood the LSA on the interface, by performing the 1705 actions in step 4 for a Backup MDR (whether or not the router 1706 is a Backup MDR on this interface). A separate BackupWait 1707 Neighbor List is created for each interface, but only one 1708 BackupWait Timer is associated with the LSA. Examine the 1709 next interface (the LSA is not immediately flooded out this 1710 interface). 1712 (7) If the optional step 6 is not performed, then the LSA is flooded 1713 out the interface. The LSA is included in an LSU packet which is 1714 multicast out the interface using the destination IP address 1715 AllSPFRouters. 1717 8.1.1. Note on Step 6 of LSA Forwarding Procedure 1719 Performing the optional Step 6 can greatly reduce flooding overhead 1720 if the LSA was received on a MANET or broadcast interface. For 1721 example, assume the LSA was received from the DR of a broadcast 1722 network that includes 100 routers, and 50 of the routers (not 1723 including the DR) are also attached to a MANET. Assume that these 50 1724 routers are neighbors of each other in the MANET, and that each has a 1725 neighbor in the MANET that is not attached to the broadcast network 1726 (and is therefore not covered). Then by performing Step 6 of the LSA 1727 forwarding procedure, the number of routers that forward the LSA from 1728 the broadcast network to the MANET is reduced from 50 to just 1 1729 (assuming that at most one of the 50 routers is an MDR). 1731 8.1.2. BackupWait Timer Expiration 1733 If the BackupWait Timer for an LSA expires, then the following steps 1734 are performed for each (MANET) interface for which a BackupWait 1735 Neighbor List exists for the LSA. 1737 (1) If the BackupWait Neighbor List for the interface contains at 1738 least one router that is currently a bidirectional neighbor, the 1739 following actions are performed. 1741 (a) The LSA is flooded out the interface. 1743 (b) If the LSA is on the Ack List for the interface (i.e., is 1744 scheduled to be included in a delayed Link State 1745 Acknowledgment packet), then the router SHOULD remove the LSA 1746 from the Ack List, since the flooded LSA will be treated as 1747 an implicit Ack. 1749 (c) If the LSA is on the Link State retransmission list for any 1750 neighbor, the retransmission SHOULD be rescheduled (if 1751 necessary) so that it does not occur within AckInterval plus 1752 propagation delays. 1754 (2) The BackupWait Neighbor list is then deleted (whether or not the 1755 LSA is flooded). 1757 8.2. Sending Link State Acknowledgments 1759 This section describes the procedure for sending Link State 1760 Acknowledgments (LS Acks) on MANET interfaces. Section 13.5 of RFC 1761 2328 remains unchanged for non-MANET interfaces, but does not apply 1762 to MANET interfaces. To minimize overhead due to LS Acks, and to 1763 take advantage of the broadcast nature of MANETs, all LS Ack packets 1764 sent on a MANET interface are multicast using the IP address 1765 AllSPFRouters. In addition, duplicate LSAs received as a multicast 1766 are not acknowledged. 1768 When a router receives an LSA, it must decide whether to send a 1769 delayed Ack, an immediate Ack, or no Ack. (However, a non-ackable 1770 LSA is never acknowledged, as described in Appendix D.) A delayed 1771 Ack may be delayed for up to AckInterval seconds, and allows several 1772 LS Acks to be grouped into a single multicast LS Ack packet. An 1773 immediate Ack is also sent in a multicast LS Ack packet, and may 1774 include other LS Acks that were scheduled to be sent as delayed Acks. 1775 The decision depends on whether the received LSA is new (i.e., is 1776 more recent than the database copy) or a duplicate (the same instance 1777 as the database copy), and on whether the LSA was received as a 1778 multicast or a unicast (which indicates a retransmitted LSA). The 1779 following rules are used to make this decision. 1781 (1) If the received LSA is new, a delayed Ack is sent on each 1782 MANET interface associated with the area, unless the LSA is 1783 flooded out the interface. 1785 (2) If the LSA is a duplicate and was received as a multicast, 1786 the LSA is not acknowledged. 1788 (3) If the LSA is a duplicate and was received as a unicast: 1790 (a) If the router is an MDR, or AdjConnectivity = 2 and the 1791 router is a Backup MDR, or AdjConnectivity = 0, then an 1792 immediate Ack is sent out the receiving interface. 1794 (b) Otherwise, a delayed Ack is sent out the receiving 1795 interface. 1797 The reason that (Backup) MDRs send an immediate Ack when a 1798 retransmitted LSA is received, is to try to prevent other adjacent 1799 neighbors from retransmitting the LSA, since (Backup) MDRs usually 1800 have a large number of adjacent neighbors. MDR Other routers do not 1801 send an immediate Ack (unless AdjConnectivity = 0) because they have 1802 fewer adjacent neighbors, and so the potential benefit does not 1803 justify the additional overhead resulting from sending immediate 1804 Acks. 1806 8.3. Retransmitting LSAs 1808 LSAs are retransmitted according to Section 13.6 of RFC 2328. Thus, 1809 LSAs are retransmitted only to adjacent routers. Therefore, since 1810 OSPF-MDR does not allow an adjacency to be formed between two MDR 1811 Other routers, an MDR Other never retransmits an LSA to another MDR 1812 Other, only to its parents, which are (Backup) MDRs. 1814 Retransmitted LSAs are included in LSU packets that are sent directly 1815 to an adjacent neighbor that did not acknowledge the LSA (explicitly 1816 or implicitly). The length of time between retransmissions is given 1817 by the configurable interface parameter RxmtInterval, whose default 1818 is 7 seconds for a MANET interface. To reduce overhead, several 1819 retransmitted LSAs should be included in a single LSU packet whenever 1820 possible. 1822 8.4. Receiving Link State Acknowledgments 1824 A Link State Acknowledgment (LS Ack) packet that is received from an 1825 adjacent neighbor (in state Exchange or greater) is processed as 1826 described in Section 13.7 of RFC 2328, with the additional steps 1827 described in this section. An LS Ack packet that is received from a 1828 neighbor in a lesser state than Exchange is discarded. 1830 Each router maintains an Acked LSA List for each adjacent neighbor, 1831 to keep track of any LSA instances the neighbor has acknowledged, but 1832 which the router itself has NOT yet received. This is necessary 1833 because (unlike RFC 2328) each router acknowledges an LSA only the 1834 first time it is received as a multicast. 1836 If the neighbor from which the LS Ack packet was received is in state 1837 Exchange or greater, then the following steps are performed for each 1838 LS Ack in the received LS Ack packet: 1840 (1) If the router does not have a database copy of the LSA being 1841 acknowledged, or has a database copy which is less recent than 1842 the one being acknowledged, the LS Ack is added to the Acked LSA 1843 List for the sending neighbor. 1845 (2) If the router has a database copy of the LSA being acknowledged, 1846 which is the same as the instance being acknowledged, then the 1847 following action is performed. For each MANET interface for which 1848 a BackupWait Neighbor List exists for the LSA (see Section 8.1), 1849 remove the sending neighbor from the BackupWait Neighbor list if 1850 it belongs to the list. 1852 9. Originating LSAs 1854 Unlike the DR of an OSPF broadcast network, an MDR does not originate 1855 a network-LSA, since a network-LSA cannot be used to describe the 1856 general topology of a MANET. Instead, each router advertises a 1857 subset of its MANET neighbors as point-to-point links in its router- 1858 LSA. The choice of which neighbors to advertise is flexible, and is 1859 determined by the configurable parameter LSAFullness. 1861 If adjacency reduction is used (AdjConnectivity is 1 or 2), then as a 1862 minimum requirement each router must advertise a minimum set of 1863 "backbone" neighbors in its router-LSA. This minimum choice 1864 corresponds to LSAFullness = 0, and results in the minimum amount of 1865 LSA flooding overhead, but does not provide routing along shortest 1866 paths. 1868 Therefore, to allow routers to calculate shortest paths, without 1869 requiring every pair of neighboring routers along the shortest paths 1870 to be adjacent (which would be inefficient due to requiring a large 1871 number of adjacencies), a router-LSA may also advertise non-adjacent 1872 neighbors that satisfy a synchronization condition described below. 1874 To motivate this, we note that OSPF already allows a non-adjacent 1875 neighbor to be a next hop, if both the router and the neighbor belong 1876 to the same broadcast network (and are both adjacent to the DR). A 1877 network-LSA for a broadcast network (which includes all routers 1878 attached to the network) implies that any router attached to the 1879 network can forward packets directly to any other router attached to 1880 the network (which is why the distance from the network to all 1881 attached routers is zero in the graph representing the link-state 1882 database). 1884 Since a network-LSA cannot be used to describe the general topology 1885 of a MANET, the only way to advertise non-adjacent neighbors that can 1886 be used as next hops, is to include them in the router-LSA. However, 1887 to ensure that such neighbors are sufficiently synchronized, only 1888 "routable" neighbors are allowed to be included in LSAs, and to be 1889 used as next hops in the SPF calculation. 1891 9.1. Routable Neighbors 1893 A bidirectional MANET neighbor becomes routable if its state is Full, 1894 or if the SPF calculation has produced a route to the neighbor and 1895 the neighbor satisfies the routable neighbor quality condition 1896 (defined below). Since only routable neighbors are advertised in 1897 router-LSAs, and since adjacencies are selected to form a connected 1898 spanning subgraph, this definition implies that there exists, or 1899 recently existed, a path of full adjacencies from the router to the 1900 routable neighbor. The idea is that, since a routable neighbor can 1901 be reached through an acceptable path, it makes sense to take a 1902 "shortcut" and forward packets directly to the routable neighbor. 1904 This requirement does not guarantee perfect synchronization, but 1905 simulations have shown that it performs well in mobile networks. 1906 This requirement avoids, for example, forwarding packets to a new 1907 neighbor that is poorly synchronized because it was not reachable 1908 before it became a neighbor. 1910 To avoid selecting poor quality neighbors as routable neighbors, a 1911 neighbor that is selected as a routable neighbor must satisfy the 1912 routable neighbor quality condition. By default, this condition is 1913 that the neighbor's BNS must include the router itself (indicating 1914 that the neighbor agrees the connection is bidirectional). 1915 Optionally, a router may impose a stricter condition. For example, a 1916 router may require that two Hellos have been received from the 1917 neighbor that (explicitly or implicitly) indicate that the neighbor's 1918 BNS includes the router itself. 1920 The single-bit neighbor variable Routable indicates whether the 1921 neighbor is routable, and is initially set to 0. If adjacency 1922 reduction is used, Routable is updated as follows when the state of 1923 the neighbor changes, or the SPF calculation finds a route to the 1924 neighbor, or a Hello is received that affects the routable neighbor 1925 quality condition. 1927 (1) If Routable is 0 for the neighbor and the state of the neighbor 1928 changes to Full, Routable is set to 1 for the neighbor. 1930 (2) If Routable is 0 for the neighbor, the state of the neighbor is 1931 2-Way or greater, there exists a route to the neighbor, and the 1932 routable neighbor quality condition (defined above) is satisfied, 1933 then Routable is set to 1 for the neighbor. 1935 (3) If Routable is 1 for the neighbor and the state of the neighbor 1936 is less than 2-Way, Routable is set to 0 for the neighbor. 1938 If adjacency reduction is not used (AdjConnectivity = 0), then a 1939 neighbor is defined to be routable if and only if its state is 1940 Full. 1942 9.2. Partial and Full-Topology LSAs 1944 The choice of which MANET neighbors to include in the router-LSA is 1945 flexible. Whether or not adjacency reduction is used, the router can 1946 originate either partial-topology or full-topology LSAs. This 1947 flexibility is made possible by defining two types of neighbors that 1948 are included in the router-LSA: backbone neighbors and selected 1949 advertised neighbors. 1951 9.2.1. Backbone Neighbors and Selected Advertised Neighbors 1953 A backbone neighbor is defined to be a bidirectional neighbor that is 1954 a Dependent Neighbor, Dependent Selector, (Backup) Parent, or child. 1955 If adjacency reduction is not used (AdjConnectivity = 0), then the 1956 set of backbone neighbors is empty (since there are no dependent 1957 neighbors or parents). 1959 If adjacency reduction is used, then a router MUST include in its 1960 router-LSA all backbone neighbors that are routable. A minimum LSA, 1961 corresponding to LSAFullness = 0, includes only these neighbors. 1962 This choice guarantees connectivity, but does not provide shortest 1963 paths. However, it may be useful in large networks to achieve 1964 maximum scalability. If adjacency reduction is not used, then 1965 LSAFullness MUST NOT be 0, since in this case the set of backbone 1966 neighbors is empty. 1968 To allow flexibility while ensuring that LSAs are symmetric (i.e., 1969 router i advertises a link to router j if and only if router j 1970 advertises a link to router i), each router maintains a selected 1971 advertised neighbor list (SANS), which consists of MANET neighbors 1972 that the router has selected to advertise in its router-LSA, not 1973 including backbone neighbors. Since the SANS does not include 1974 Dependent Neighbors, the lists SANS and DNS are disjoint. (Note that 1975 both lists are advertised in Hellos.) 1977 If LSAFullness = 0, then the SANS is empty, since only backbone 1978 neighbors are included in the router-LSA. At the other extreme, a 1979 full-topology LSA, corresponding to LSAFullness = 4, includes all 1980 routable neighbors. In this case, the SANS includes all 1981 bidirectional MANET neighbors except backbone neighbors. Note that 1982 backbone neighbors and neighbors in the SANS need not be routable, 1983 but only routable neighbors may be included in the router-LSA. (This 1984 is done so that the SANS, which is advertised in Hellos, does not 1985 depend on routability.) 1987 9.2.2. Choice of LSAFullness 1989 LSAFullness affects the contents of the router-LSA by determining the 1990 neighbors to include in the SANS. The choices of SANS corresponding 1991 to the extreme cases of LSAFullness equal to 0 and 4 were described 1992 above. 1994 If LSAFullness is 1 or 2, the router originates min-cost LSAs, which 1995 are partial-topology LSAs that (when flooded) provide each router 1996 with sufficient information to calculate at least one shortest 1997 (minimum-cost) path to each destination. If LSAFullness is 2, then 1998 additional MANET neighbors are also included in the router-LSA to 1999 provide redundant routes. 2001 Appendix C describes the algorithm for selecting the neighbors to 2002 include in the SANS that results in min-cost LSAs. The input to this 2003 algorithm includes information obtained from Hellos received from 2004 each MANET neighbor, including the Bidirectional Neighbor List (BNS), 2005 Dependent Neighbor Set (DNS), Selected Advertised Neighbor List 2006 (SANS), and the Metric TLV. The Metric TLV, specified in Section 2007 A.2.2.8, is included in each Hello and advertises the link cost to 2008 each bidirectional neighbor. To minimize overhead, it allows the 2009 option of advertising only a single metric for the interface (equal 2010 to the link cost to each neighbor). 2012 If LSAFullness is 3, each (Backup) MDR originates a full LSA (which 2013 includes all routable neighbors), while each MDR Other originates a 2014 minimum LSA (which includes only routable backbone neighbors). If a 2015 router has multiple MANET interfaces, its LSA includes all routable 2016 neighbors on the interfaces for which it is a (Backup) MDR, and 2017 includes only routable backbone neighbors on its other interfaces. 2018 When a router changes its MDR Level from MDR Other to (Backup) MDR on 2019 a given interface, it must originate a new LSA. This choice provides 2020 routing along nearly shortest paths with relatively low overhead. 2022 It is not necessary for different routers to choose the same value of 2023 LSAFullness; the different choices are interoperable because they all 2024 require the router-LSA to include a minimum set of neighbors, and 2025 because the construction of the router-LSA (described below) ensures 2026 that the router-LSAs originated by different routers are consistent. 2028 9.2.3. Construction of the Router-LSA 2030 When a new router-LSA is originated, it includes a point-to-point 2031 (type 1) link for each MANET neighbor j that is routable and 2032 satisfies at least one of the following three conditions: 2034 (1) The router's SANS (for any interface) includes j. 2036 (2) Neighbor j's SANS includes the router (to ensure symmetry). 2038 (3) Neighbor j is a backbone neighbor. 2040 Note that if adjacency reduction is not used (AdjConnectivity = 0), 2041 then the set of backbone neighbors is empty, and a MANET neighbor is 2042 routable if and only if it is in the Full state. Also note that 2043 neighbors in the SANS need not be routable, but only routable 2044 neighbors are included in the router-LSA. 2046 A new router-LSA is originated if any of the events specified in 2047 Section 12.4 of [RFC2328] occurs, except that event (4), i.e., one of 2048 the neighboring routers changes to/from the FULL state, does not 2049 apply to MANET neighbors. For MANET neighbors, event (4) is replaced 2050 with the following two events: 2052 o There exists a routable MANET neighbor j that satisfies one of the 2053 above three conditions, but is not included in the current router- 2054 LSA. 2056 o The current router-LSA includes a MANET neighbor that is no longer 2057 routable. 2059 If AdjConnectivity = 0 and LSAFullness = 4 (full LSAs), then since 2060 only Full neighbors are routable and the SANS includes all 2061 bidirectional neighbors in this case, the above two events are 2062 equivalent to one of the neighboring routers changing to/from the 2063 Full state. 2065 10. Calculating the Routing Table 2067 The routing table calculation is the same as specified in RFC 2328, 2068 except for the following change to Section 16.1 (Calculating the 2069 shortest-path tree for an area). 2071 Recall from Section 9 that a router can use any routable neighbor as 2072 a next hop to a destination. However, unless LSAFullness = 4 (full- 2073 topology LSAs), the router-LSA originated by the router usually does 2074 not include all routable neighbors. Therefore, the shortest-path 2075 tree calculation described in Section 16.1 of RFC 2328 must be 2076 modified to allow any routable neighbor on a MANET interface to be 2077 used as a next hop. This is accomplished by modifying step 2 so that 2078 the router-LSA associated with the root vertex (i.e., the router 2079 doing the calculation) is augmented to include all routable neighbors 2080 on each MANET interface. In addition, step 2b (checking for a link 2081 from W back to V) must be skipped when V is the root vertex and W is 2082 a routable MANET neighbor whose state is less than Full. However, 2083 step 2b MUST be executed when W is in state Full and when V is not 2084 the root vertex, to ensure that Full neighbors are synchronized in 2085 both directions, and to ensure compatibility with OSPFv3. 2087 Note that, if LSAFullness is less than 4, then the set of routable 2088 neighbors can change without causing the contents of the router-LSA 2089 to change. This could happen, for example, if a routable neighbor 2090 that was not included in the router-LSA transitions to the Down or 2091 Init state. Therefore, if the set of routable neighbors changes, the 2092 shortest-path tree must be recalculated even if the router-LSA does 2093 not change. 2095 After the shortest-path tree and routable table are calculated, the 2096 set of routable neighbors must be updated, since a route to a non- 2097 routable neighbor may have been discovered. If the set of routable 2098 neighbors changes, then the shortest-path tree and routing table must 2099 be calculated a second time. The second calculation will not change 2100 the set of routable neighbors again, so two calculations are 2101 sufficient. 2103 11. Security Considerations 2105 This document proposes an extension of OSPFv3 and can use the same 2106 IPv6 security mechanisms as OSPFv3. Hence, this document does not 2107 raise any new security concerns. 2109 12. IANA Considerations 2111 This document defines three new LLS TLV types (see Section A.2) to be 2112 allocated by IANA. 2114 13. Acknowledgments 2116 Thanks to Aniket Desai for helpful discussions and comments, 2117 including the suggestion that Router Priority should come before MDR 2118 Level in the lexicographical comparison of (RtrPri, MDR Level, RID) 2119 when selecting MDRs and BMDRs, and that the MDR calculation should be 2120 repeated if it causes the MDR Level to change. Thanks also to Tom 2121 Henderson for helpful discussions and comments. 2123 14. Normative References 2125 [RFC2328] J. Moy. "OSPF Version 2", RFC 2328, April 1998. 2127 [RFC2740] R. Coltun, D. Ferguson, and J. Moy. "OSPF for IPv6", RFC 2128 2740, December 1999. 2130 [LLS] A. Zinin, A. Roy, L. Nguyen, B. Friedman, and D. Young, "OSPF 2131 Link-local Signaling", draft-ietf-ospf-lls-03.txt (work in 2132 progress), August 2007. 2134 [RFC2119] Bradner, S., "Key words for use in RFC's to Indicate 2135 Requirement Levels", RFC 2119, March 1997. 2137 15. Informative References 2139 [Lawler] E. Lawler. "Combinatorial Optimization: Networks and 2140 Matroids", Holt, Rinehart, and Winston, New York, 1976. 2142 [Suurballe] J.W. Suurballe and R.E. Tarjan. "A Quick Method for 2143 Finding Shortest Pairs of Disjoint Paths", Networks, Vol. 14, 2144 pp. 325-336, 1984. 2146 A. Packet Formats 2148 A.1. Options Field 2150 A new bit, called L (for LLS) is introduced to OSPFv3 Options field 2151 (see Figure A.1). The mask for the bit is 0x200. Routers set the L 2152 bit in Hello and DD packets to indicate that the packet contains LLS 2153 data block. Routers set the L bit in a self-originated router-LSA to 2154 indicate that the LSA is non-ackable. 2156 0 1 2 2157 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 2158 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+-+-+--+--+--+--+--+--+ 2159 | | | | | | | | | | | | | | |L|AF|*|*|DC| R| N|MC| E|V6| 2160 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+-+-+--+--+--+--+--+--+ 2162 Figure A.1: The Options field 2164 A.2. Link-Local Signaling 2166 Link-local signaling (LLS) [LLS] describes an extension to OSPFv2 and 2167 OSPFv3 which allows the exchange of arbitrary data using existing, 2168 standard OSPF packet types. Here we use LLS for OSPFv3, which is 2169 accomplished by adding an LLS data block at the end of the OSPFv3 2170 packet. 2172 The IPv6 header length includes the total length of the OSPFv3 2173 header, OSPFv3 data, and LLS data, but the OSPFv3 header does not 2174 contain the LLS data length in its length field. The IPv6 packet 2175 format is depicted in Figure A.2 below. 2177 +---------------------+ -- 2178 | IPv6 Header | ^ 2179 | Length = HL+X+Y | | Header Length = HL 2180 | | v 2181 +---------------------+ -- 2182 | OSPFv3 Header | ^ 2183 | Length = X | | 2184 |.....................| | X 2185 | | | 2186 | OSPFv3 Data | | 2187 | | v 2188 +---------------------+ -- 2189 | | ^ 2190 | LLS Data | | Y 2191 | | v 2192 +---------------------+ -- 2194 Figure A.2: Attaching LLS Data Block 2196 The LLS data block may be attached to OSPFv3 Hello and Database 2197 Description (DD) packets. The data included in the LLS block 2198 attached to a Hello packet may be used for dynamic signaling, since 2199 Hello packets may be sent at any moment in time. However, delivery of 2200 LLS data in Hello packets is not guaranteed. The data sent with DD 2201 packets is guaranteed to be delivered as part of the adjacency 2202 forming process. 2204 A.2.1 LLS Data Block 2206 The data block used for link-local signaling is formatted as 2207 described below (see Figure A.3). 2209 0 1 2 3 2210 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 2211 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2212 | Checksum | LLS Data Length | 2213 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2214 | | 2215 | LLS TLVs | 2216 . . 2217 . . 2218 . . 2219 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2220 Figure A.3: Format of LLS Data Block 2222 The Checksum field contains the standard IP checksum of the entire 2223 contents of the LLS block. 2225 The 16-bit LLS Data Length field contains the length (in 32-bit 2226 words) of the LLS block including the header and payload. 2227 Implementations should not use the Length field in the IPv6 packet 2228 header to determine the length of the LLS data block. 2230 The rest of the block contains a set of Type/Length/Value (TLV) 2231 triplets as described in the following section. All TLVs must be 2232 32-bit aligned (with padding if necessary). 2234 A.2.2 LLS TLV Format 2236 The contents of LLS data block is constructed using TLVs. See Figure 2237 A.4 for the TLV format. 2239 The type field contains the TLV ID which is unique for each type of 2240 TLVs. The Length field contains the length of the Value field (in 2241 bytes) that is variable and contains arbitrary data. 2243 0 1 2 3 2244 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 2245 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2246 | Type | Length | 2247 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2248 | | 2249 . . 2250 . Value . 2251 . . 2252 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2253 Figure A.4: Format of LLS TLVs 2255 Note that TLVs are always padded to 32-bit boundary, but padding 2256 bytes are not included in TLV Length field (though it is included in 2257 the LLS Data Length field of the LLS block header). All unknown TLVs 2258 MUST be silently ignored. 2260 A.2.3 Hello TLV 2262 The Hello TLV is appended to each MANET Hello. It includes the 2263 current Hello sequence number (HSN) for the transmitting interface 2264 and the number of neighbors of each type that are listed in the body 2265 of the Hello (see Section 4.1). It also indicates whether the Hello 2266 is full or differential (via the D-bit), and whether AdjConnectivity 2267 is 0 (via the A-bit). 2269 0 1 2 3 2270 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 2271 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2272 | Type | Length | 2273 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2274 | Hello Sequence Number | Reserved |A|D| 2275 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2276 | N1 | N2 | N3 | N4 | 2277 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2279 o Type: Set to 14. 2280 o Length: Set to 8. 2281 o Hello Sequence Number: A circular two octet unsigned integer 2282 indicating the current HSN for the transmitting interface. The 2283 HSN for the interface MUST be incremented by 1 every time a 2284 (differential or full) Hello is sent on the interface. 2285 o Reserved: Set to 0. Reserved for future use. 2286 o A (1 bit): Set to 1 if AdjConnectivity is 0, otherwise set to 0. 2287 o D (1 bit): Set to 1 for a differential Hello and 0 for a full 2288 Hello. 2289 o N1 (8 bits): The number of neighbors listed in the Hello that 2290 are in state Down. N1 is zero if the the Hello is not 2291 differential. 2292 o N2 (8 bits): The number of neighbors listed in the Hello that 2293 are in state Init. 2294 o N3 (8 bits): The number of neighbors listed in the Hello that 2295 are Dependent. 2296 o N4 (8 bits): The number of neighbors listed in the Hello that 2297 are Selected Advertised Neighbors. 2299 A.2.4 MDR TLV 2301 A new TLV is defined which includes the same two Router IDs that are 2302 included in the DR and Backup DR fields of a Hello sent by the 2303 router. This TLV is used in conjunction with a Database Description 2304 packet, and is used to indicate the router's MDR Level and selected 2305 parent(s). 2307 0 1 2 3 2308 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 2309 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2310 | Type | Length | 2311 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2312 | DR | 2313 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2314 | Backup DR | 2315 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2316 o Type: Set to 15. 2317 o Length: Set to 8. 2318 o DR: The same Router ID that is included in the DR field of a 2319 Hello sent by the router (see Section A.3). 2320 o Backup DR: The same Router ID that is included in the Backup DR 2321 field of a Hello sent by the router (see Section A.3). 2323 A.2.5 Metric TLV 2325 If LSAFullness is 1 or 2, the Metric TLV is appended to each MANET 2326 Hello packet. It provides the link metric for each bidirectional 2327 neighbor listed in the body of the Hello. At a minimum, this TLV 2328 advertises a single default metric. If the I bit is set, the Router 2329 ID and link metric are included for each bidirectional neighbor 2330 listed in the body of the Hello whose link metric is not equal to the 2331 default metric. This option reduces overhead when all neighbors have 2332 the same link metric, or only a few neighbors have a link metric that 2333 differs from the default metric. If the I bit is zero, the link 2334 metric is included for each bidirectional neighbor that is listed in 2335 the body of the Hello and the neighbor RIDs are omitted from the TLV. 2337 0 1 2 3 2338 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 2339 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2340 | Type | Length | 2341 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2342 | Default Metric | Reserved |I| 2343 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2344 | Neighbor ID (1) | 2345 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2346 | Neighbor ID (2) | 2347 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2348 | ... | 2349 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2350 | Metric (1) | Metric (2) | 2351 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2352 | ... 2353 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2355 o Type: Set to 16. 2356 o Length: Set to 4 + 6*N if the I bit is 1, and to 4 + 2*N if the I 2357 bit is 0, where N is the number of neighbors included in the TLV. 2358 o Default Metric: If the I bit is 1, this is the link metric that 2359 applies to every bidirectional neighbor listed in the body of 2360 the Hello whose RID is not listed in the Metric TLV. 2361 o Neighbor ID: If the I bit is 1, the RID is listed for each 2362 bidirectional neighbor (Lists 3 through 5 as defined in 2363 Section 4.1) in the body of the Hello whose link metric is not 2364 equal to the default metric. Omitted if the I bit is 0. 2365 o Metric: Link metric for each bidirectional neighbor, listed in 2366 the same order as the Neighbor IDs in the TLV if the I bit is 1, 2367 and in the same order as the Neighbor IDs of bidirectional 2368 neighbors (Lists 3 through 5 as defined in Section 4.1) 2369 in the body of the Hello if the I bit is 0. 2371 A.3. Hello Packet DR and Backup DR Fields 2373 The Designated Router (DR) and Backup DR fields of a Hello packet are 2374 set as follows: 2376 o DR: This field is the router's MDR Parent, or is 0.0.0.0 if the 2377 MDR Parent is null. The MDR Parent of an MDR is always the 2378 router's own RID. 2380 o Backup DR: This field is the router's Backup MDR Parent, or is 2381 0.0.0.0 if the Backup MDR Parent is null. The Backup MDR Parent 2382 of a BMDR is always the router's own RID. 2384 A.4. LSA Formats and Examples 2386 LSA formats are specified in [RFC2740] Section 3.4.3. Figure A.5 2387 below gives an example network map for a MANET in a single area. 2389 o Four MANET nodes RT1, RT2, RT3, and RT4 are in area 1. 2390 o RT1's MANET interface has links to RT2 and RT3's MANET interfaces. 2391 o RT2's MANET interface has links to RT1 and RT3's MANET interfaces. 2392 o RT3's MANET interface has links to RT1, RT2, and RT3's MANET 2393 interfaces. 2394 o RT4's MANET interface has a link to RT3's MANET interface. 2395 o RT1 and RT2 have stub networks attached on broadcast interfaces. 2396 o RT3 has a transit network attached on a broadcast interface. 2398 .......................................... 2399 . Area 1. 2400 . + . 2401 . | . 2402 . | 2+---+1 1+---+ 2403 . N1 |--|RT1|-----+ +---|RT4|---- 2404 . | +---+ | / +---+ 2405 . | | / . 2406 . + | N3 / . 2407 . | / . 2408 . + | / . 2409 . | | / . 2410 . | 2+---+1 | / . 2411 . N2 |--|RT2|-----+-------+ . 2412 . | +---+ |1 . 2413 . | +---+ . 2414 . | |RT3|---------------- 2415 . + +---+ . 2416 . |2 . 2417 . +------------+ . 2418 . |1 N4 . 2419 . +---+ . 2420 . |RT5| . 2421 . +---+ . 2422 .......................................... 2424 Figure A.5: Area 1 with IP addresses shown 2426 Network IPv6 prefix 2427 ----------------------------------- 2428 N1 5f00:0000:c001:0200::/56 2429 N2 5f00:0000:c001:0300::/56 2430 N4 5f00:0000:c001:0400::/56 2432 Table 1: IPv6 link prefixes for sample network 2433 Router interface Interface ID IPv6 global unicast prefix 2434 ----------------------------------------------------------- 2435 RT1 LOOPBACK 0 5f00:0001::/64 2436 to N3 1 n/a 2437 to N1 2 5f00:0000:c001:0200::RT1/56 2438 RT2 LOOPBACK 0 5f00:0002::/64 2439 to N3 1 n/a 2440 to N2 2 5f00:0000:c001:0300::RT2/56 2441 RT3 LOOPBACK 0 5f00:0003::/64 2442 to N3 1 n/a 2443 to N4 2 5f00:0000:c001:0400::RT3/56 2444 RT4 LOOPBACK 0 5f00:0004::/64 2445 to N3 1 n/a 2446 RT5 to N4 1 5f00:0000:c001:0400::RT5/56 2448 Table 2: IPv6 link prefixes for sample network 2450 Router interface Interface ID link-local address 2451 ------------------------------------------------------- 2452 RT1 LOOPBACK 0 n/a 2453 to N1 1 fe80:0001::RT1 2454 to N3 2 fe80:0002::RT1 2455 RT2 LOOPBACK 0 n/a 2456 to N2 1 fe80:0001::RT2 2457 to N3 2 fe80:0002::RT2 2458 RT3 LOOPBACK 0 n/a 2459 to N3 1 fe80:0001::RT3 2460 to N4 2 fe80:0002::RT3 2461 RT4 LOOPBACK 0 n/a 2462 to N3 1 fe80:0001::RT4 2463 RT5 to N4 1 fe80:0002::RT5 2465 Table 3: OSPF Interface IDs and link-local addresses 2467 A.4.1 Router-LSAs 2469 As an example, consider the router-LSA that node RT3 would originate. 2470 The node consists of one MANET, one broadcast, and one loopback 2471 interface. 2473 RT3's router-LSA 2475 LS age = DoNotAge+0 ;newly originated 2476 LS type = 0x2001 ;router-LSA 2477 Link State ID = 0 ;first fragment 2478 Advertising Router = 192.1.1.3 ;RT3's Router ID 2479 bit E = 0 ;not an AS boundary router 2480 bit B = 1 ;area border router 2481 Options = (V6-bit|E-bit|R-bit) 2482 Type = 1 ;p2p link to RT1 2483 Metric = 11 ;cost to RT1 2484 Interface ID = 1 ;Interface ID 2485 Neighbor Interface ID = 1 ;Interface ID 2486 Neighbor Router ID = 192.1.1.1 ;RT1's Router ID 2487 Type = 1 ;p2p link to RT2 2488 Metric = 12 ;cost to RT2 2489 Interface ID = 1 ;Interface ID 2490 Neighbor Interface ID = 1 ;Interface ID 2491 Neighbor Router ID = 192.1.1.2 ;RT2's Router ID 2492 Type = 1 ;p2p link to RT4 2493 Metric = 13 ;cost to RT4 2494 Interface ID = 1 ;Interface ID 2495 Neighbor Interface ID = 1 ;Interface ID 2496 Neighbor Router ID = 192.1.1.4 ;RT4's Router ID 2497 Type = 2 ;connects to N4 2498 Metric = 1 ;cost to N4 2499 Interface ID = 2 ;RT3's Interface ID 2500 Neighbor Interface ID = 1 ;RT5's Interface ID (elected DR) 2501 Neighbor Router ID = 192.1.1.5 ;RT5's Router ID (elected DR) 2503 A.4.2 Link-LSAs 2505 Consider the link-LSA that RT3 would originate for its MANET 2506 interface. 2508 RT3's Link-LSA for its MANET interface 2510 LS age = DoNotAge+0 ;newly originated 2511 LS type = 0x0008 ;Link-LSA 2512 Link State ID = 1 ;Interface ID 2513 Advertising Router = 192.1.1.3 ;RT3's Router ID 2514 RtrPri = 1 ;default priority 2515 Options = (V6-bit|E-bit|R-bit) 2516 Link-local Interface Address = fe80:0001::RT3 2517 # prefixes = 0 ;no global unicast address 2519 A.4.3 Intra-Area-Prefix-LSAs 2521 A MANET node originates an intra-area-prefix-LSA to advertise its own 2522 prefixes, and those of its attached networks or stub links. As an 2523 example, consider the intra-area-prefix-LSA that RT3 will build. 2525 RT2's intra-area-prefix-LSA for its own prefixes 2527 LS age = DoNotAge+0 ;newly originated 2528 LS type = 0x2009 ;intra-area-prefix-LSA 2529 Link State ID = 177 ;or something 2530 Advertising Router = 192.1.1.3 ;RT3's Router ID 2531 # prefixes = 2 2532 Referenced LS type = 0x2001 ;router-LSA reference 2533 Referenced Link State ID = 0 ;always 0 for router-LSA reference 2534 Referenced Advertising Router = 192.1.1.3 ;RT2's Router ID 2535 PrefixLength = 64 ;prefix on RT3's LOOPBACK 2536 PrefixOptions = 0 2537 Metric = 0 ;cost of RT3's LOOPBACK 2538 Address Prefix = 5f00:0003::/64 2539 PrefixLength = 56 ;prefix on RT3's interface 2 2540 PrefixOptions = 0 2541 Metric = 1 ;cost of RT3's interface 2 2542 Address Prefix = 5f00:0000:c001:0400::RT3/56 ;pad 2544 B. Detailed Algorithms for MDR/BMDR Selection 2546 This section provides detailed algorithms for Step 2.4 of Phase 2 2547 (MDR Selection) and Step 3.2 of Phase 3 (BMDR Selection) of the MDR 2548 selection algorithm described in Section 5. Step 2.4 uses a breadth- 2549 first search (BFS) algorithm, and Step 3.2 uses an efficient 2550 algorithm for finding pairs of node-disjoint paths from Rmax to all 2551 other neighbors. Both algorithms run in O(d^2) time, where d is the 2552 number of neighbors. 2554 For convenience, in the following description, the term "bi-neighbor" 2555 will be used as an abbreviation for "bidirectional neighbor". Also, 2556 node i denotes the router performing the calculation. 2558 B.1. Detailed Algorithm for Step 2.4 (MDR Selection) 2560 The following algorithm performs Step 2.4 of the MDR selection 2561 algorithm, and assumes that Phase 1 and Steps 2.1 through 2.3 have 2562 been performed, so that the neighbor connectivity matrix NCM has been 2563 computed, and Rmax is the bi-neighbor with the (lexicographically) 2564 largest value of (RtrPri, MDR Level, RID). The BFS algorithm uses a 2565 FIFO queue so that all nodes 1 hop from node Rmax are processed 2566 first, then 2 hops, etc. When the BFS algorithm terminates, hops(u), 2567 for each bi-neighbor node u of node i, will be equal to the minimum 2568 number of hops from node Rmax to node u, using only intermediate 2569 nodes that are bi-neighbors of node i and that have a larger value of 2570 (RtrPri, MDR Level, RID) than node i. The algorithm also computes, 2571 for each node u, the tree parent p(u) and the second node r(u) on the 2572 tree path from Rmax to u, which will be used in Step 3.2 2574 (a) Compute a matrix of link costs c(u,v) for each pair of 2575 bi-neighbors u and v as follows: If node u has a larger value 2576 of (RtrPri, MDR Level, RID) than node i, and NCM(u,v) = 1, 2577 then set c(u,v) to 1. Otherwise, set c(u,v) to infinity. 2578 (Note that the matrix NCM(u,v) is symmetric, but the matrix 2579 c(u,v) is not.) 2581 (b) Set hops(u) = infinity for all bi-neighbors u other than Rmax, 2582 and set hops(Rmax) = 0. Initially, p(u) is undefined for each 2583 neighbor u. For each bi-neighbor u such that c(Rmax,u) = 1, 2584 set r(u) = u; for all other u, r(u) is initially undefined. 2585 Add node Rmax to the FIFO queue. 2587 (c) While the FIFO queue is nonempty: 2588 Remove the node at the head of the queue; call it node u. 2589 For each bi-neighbor v of node i such that c(u,v) = 1: 2590 If hops(v) > hops(u) + 1, then set hops(v) = hops(u) + 1, 2591 set p(v) = u, set r(v) = r(u) if hops(v) > 1, and add 2592 node v to the tail of the queue. 2594 B.2. Detailed Algorithm for Step 3.2 (BMDR Selection) 2596 Step 3.2 of the MDR selection algorithm requires the router to 2597 determine whether there exist two node-disjoint paths from Rmax to 2598 each other bi-neighbor u, via bi-neighbors that have a larger value 2599 of (RtrPri, MDR Level, RID) than the router itself. This information 2600 is needed to determine whether the router should select itself as a 2601 BMDR. 2603 It is possible to determine separately for each bi-neighbor u whether 2604 there exist two node-disjoint paths from Rmax to u, using the well- 2605 known augmenting path algorithm [Lawler] which runs in O(n^2) time, 2606 but this must be done for all bi-neighbors u, thus requiring a total 2607 run time of O(n^3). The algorithm described below makes the same 2608 determination simultaneously for all bi-neighbors u, achieving a much 2609 faster total run time of O(n^2). The algorithm is a simplified 2610 variation of the Suurballe-Tarjan algorithm [Suurballe] for finding 2611 pairs of disjoint paths. 2613 The algorithm described below uses the following output of Phase 2: 2615 the tree parent p(u) of each node (which defines the BFS tree 2616 computed in Phase 2), and the second node r(u) on the tree path from 2617 Rmax to u. 2619 The algorithm uses the following concepts. For any node u on the BFS 2620 tree other than Rmax, we define g(u) to be the first labeled node on 2621 the reverse tree path from u to Rmax, if such a labeled node exists 2622 other than Rmax. (The reverse tree path consists of u, p(u), 2623 p(p(u)), ..., Rmax.) If no such labeled node exists, then g(u) is 2624 defined to be r(u). In particular, if u is labeled then g(u) = u. 2625 Note that g(u) either must be labeled or must be a neighbor of Rmax. 2627 For any node k that either is labeled or is a neighbor of Rmax, we 2628 define the unlabeled subtree rooted at k, denoted S(k), to be the set 2629 of nodes u such that g(u) = k. Thus, S(k) includes node k itself and 2630 the set of unlabeled nodes downstream of k on the BFS tree that can 2631 be reached without going through any labeled nodes. This set can be 2632 obtained in linear time using a depth-first search starting at node 2633 k, and using labeled nodes to indicate the boundaries of the search. 2634 Note that g(u) and S(k) are not maintained as variables in the 2635 algorithm given below, but simply refer to the definitions given 2636 above. 2638 The BMDR algorithm maintains a set B, which is initially empty. A 2639 node u is added to B when it is known that two node-disjoint paths 2640 exist from Rmax to u via nodes that have a larger value of (RtrPri, 2641 MDR Level, RID) than the router itself. When the algorithm 2642 terminates, B consists of all nodes that have this property. 2644 The algorithm consists of the following two steps. 2646 (a) Mark Rmax as labeled. For each pair of nodes u, v on the BFS 2647 tree other than Rmax such that r(u) is not equal to r(v) (i.e., 2648 u and v have different second nodes), NCM(u,v) = 1, and node u 2649 has a greater value of (RtrPri, MDR level, RID) than the router 2650 itself, add v to B. (Clearly there are two disjoint paths from 2651 Rmax to v.) 2653 (b) While there exists a node in B that is not labeled, do the 2654 following. Choose any node k in B that is not labeled, and let 2655 j = g(k). Now mark k as labeled. (This creates a new unlabeled 2656 subtree S(k), and makes S(j) smaller by removing S(k) from it.) 2657 For each pair of nodes u, v such that u is in S(k), v is in 2658 S(j), and NCM(u,v) = 1: 2660 o If u has a larger value of (RtrPri, MDR level, RID) than the 2661 router itself, and v is not in B, then add v to B. 2663 o If v has a larger value of (RtrPri, MDR level, RID) than the 2664 router itself, and u is not in B, then add u to B. 2666 A simplified version of the algorithm MAY be performed by omitting 2667 step (b). However, the simplified algorithm will result in more 2668 BMDRs, and is not recommended if AdjConnectivity = 2 since it will 2669 result in more adjacencies. 2671 The above algorithm can be executed in O(n^2) time, where n is the 2672 number of neighbors. Step (a) clearly requires O(n^2) time since it 2673 considers all pairs of nodes u and v. Step (b) also requires O(n^2) 2674 time because each pair of nodes is considered at most once. This is 2675 because labeling nodes divides unlabeled subtrees into smaller 2676 unlabeled subtrees, and a given pair u, v is considered only the 2677 first time u and v belong to different unlabeled subtrees. 2679 C. Min-Cost LSA Algorithm 2681 This section describes the algorithm for determining which MANET 2682 neighbors to include in the router-LSA when LSAFullness is 1 or 2. 2683 The min-cost LSA algorithm ensures that the link-state database 2684 provides sufficient information to calculate at least one shortest 2685 (minimum-cost) path to each destination. If LSAFullness is 2, then 2686 additional MANET neighbors are also included in the router-LSA to 2687 provide redundant routes. The algorithm assumes that a router may 2688 have multiple interfaces, at least one of which is a MANET interface. 2689 The algorithm becomes significantly simpler if the router has only a 2690 single (MANET) interface. 2692 The input to this algorithm includes information obtained from Hellos 2693 received from each neighbor on each MANET interface, including the 2694 neighbor's Bidirectional Neighbor Set (BNS), Dependent Neighbor Set 2695 (DNS), Selected Advertised Neighbor Set (SANS), and link metrics. 2696 The input also includes the link-state database if the router has a 2697 non-MANET interface. 2699 The output of the algorithm is the router's SANS for each MANET 2700 interface. The SANS is used to determine the contents of the router- 2701 LSA as described in Section 9.2.3. The min-cost LSA algorithm must 2702 be run to update the SANS (and possibly originate a new router-LSA) 2703 whenever any of the following events occurs: 2705 o The state or routability of a neighbor changes. 2706 o A Hello received from a neighbor indicates a change in its 2707 MDR Level, Router Priority, FullHelloRcvd, BNS, DNS, SANS, 2708 MDR Parent(s), or link metrics. 2709 o An LSA originated by a non-MANET neighbor is received. 2711 Although the algorithm described below runs in O(d^3) time, where d 2712 is the number of neighbors, an incremental version for a single 2713 topology change runs in O(d^2) time, as discussed following the 2714 algorithm description. 2716 For convenience, in the following description, the term "bi-neighbor" 2717 will be used as an abbreviation for "bidirectional neighbor". Also, 2718 router i will denote the router doing the calculation. To perform 2719 the min-cost LSA algorithm, the following steps are performed. 2721 (1) Create the neighbor connectivity matrix (NCM) for each MANET 2722 interface, as described in Section 5.1. Create the multiple- 2723 interface neighbor connectivity matrix MNCM as follows. For each 2724 bi-neighbor j, set MNCM(i,j) = MNCM(j,i) = 1. For each pair j, k 2725 of MANET bi-neighbors, set MNCM(j,k) = 1 if NCM(j,k) equals 1 for 2726 any MANET interface. For each pair j, k of non-MANET bi- 2727 neighbors, set MNCM(j,k) = 1 if the link-state database indicates 2728 that a direct link exists between j and k. Otherwise, set 2729 MNCM(j,k) = 0. (Note that a given router can be a neighbor on 2730 both a MANET interface and a non-MANET interface.) 2732 (2) Create the inter-neighbor cost matrix (COST) as follows. For 2733 each pair j, k of routers such that each of j and k is a bi- 2734 neighbor or router i itself: 2736 (a) If MNCM(j,k) = 1, set COST(j,k) to the metric of the link 2737 from j to k obtained from j's Hellos (for a MANET interface), 2738 or from the link-state database (for a non-MANET interface). 2739 If there are multiple links from j to k (via multiple 2740 interfaces), COST(j,k) is set to the minimum cost of these 2741 links. 2743 (b) Otherwise, set COST(j,k) to LSInfinity. 2745 (3) Create the backbone neighbor matrix (BNM) as follows. BNM 2746 indicates which pairs of MANET bi-neighbors are backbone 2747 neighbors of each other, as defined in Section 9.2.1. If 2748 adjacency reduction is not used (AdjConnectivity = 0), set all 2749 entries of BNM to zero and proceed to step 4. 2751 In the following, if a link exists from router j to router k on 2752 more than one interface, we consider only interfaces for which 2753 the cost from j to k equals COST(j,k); such interfaces will be 2754 called "candidate" interfaces. 2756 For each pair j, k of MANET bi-neighbors, BNM(j,k) is set to 1 if 2757 j and k are backbone neighbors of each other on a candidate MANET 2758 interface. That is, BNM(j,k) is set to 1 if, for any candidate 2759 MANET interface, NCM(j,k) = 1 and either of the following 2760 conditions is satisfied: 2762 (a) Router k is included in j's DNS or router j is included in 2763 k's DNS. 2765 (b) Router j is the (Backup) Parent of router k or router k is 2766 the (Backup) Parent of router j. 2768 Otherwise, BNM(j,k) is set to 0. 2770 (4) Create the selected advertised neighbor matrix (SANM) as follows. 2771 For each pair j, k of routers such that each of j and k is a bi- 2772 neighbor or router i itself, SANM(j,k) is set to 1 if, for any 2773 candidate MANET interface, NCM(j,k) = 1 and k is included in j's 2774 SANS. Otherwise, SANM(j,k) is set to 0. Note that SANM(i,k) is 2775 set to 1 if k is currently a selected advertised neighbor. 2777 (5) Compute the new set of selected advertised neighbors as follows. 2778 For each MANET bi-neighbor j, initialize the bit variable 2779 new_sel_adv(j) to 0. (This bit will be set to 1 if j is 2780 selected.) For each MANET bi-neighbor j: 2782 (a) If j is a bi-neighbor on more than one interface, consider 2783 only candidate interfaces (for which the cost to j is 2784 minimum). If one of the candidate interfaces is a non-MANET 2785 interface, examine the next neighbor (j is not selected since 2786 it will be advertised anyway). 2788 (b) If adjacency reduction is used, and one of the candidate 2789 interfaces is a MANET interface on which j is a backbone 2790 neighbor (see Section 9.2), examine the next neighbor (j is 2791 not selected since it will be advertised anyway). 2793 (c) Otherwise, if there is more than one candidate MANET 2794 interface, select the "preferred" interface by using the 2795 following preference rules in the given order: an interface 2796 is preferred if (1) router i's SANS for that interface 2797 already includes j, (2) router i's Router Priority is larger 2798 on that interface, and (3) router i's MDR level is larger on 2799 that interface. 2801 (d) This step is optional, but SHOULD be performed in order to 2802 remove redundant advertised neighbors. If SANM(i,j) = 0, 2803 i.e., j is not currently a selected advertised neighbor, then 2804 proceed to step (e). 2806 Otherwise, for each bi-neighbor k (on any interface) such 2807 that COST(k,j) > COST(k,i) + COST(i,j), determine whether 2808 there exists another bi-neighbor u such that either COST(k,u) 2809 + COST(u,j) < COST(k,i) + COST(i,j), or COST(k,u) + COST(u,j) 2810 = COST(k,i) + COST(i,j) and any of the following three 2811 conditions is true: 2813 o BNM(u,j) = 1, 2814 o SANM(j,u) > SANM(j,i), or 2815 o SANM(j,u) = SANM(j,i), SANM(u,j) = 1, and 2816 (RtrPri(u), MDR_Level(u), RID(u)) is lexicographically 2817 less than (RtrPri(i), MDR_Level(i), RID(i)). 2819 If for each such bi-neighbor k, there exists such a bi- 2820 neighbor u, then do not select j, skip step (e), and continue 2821 to the next neighbor j. 2823 (e) For each bi-neighbor k (on any interface) such that COST(k,j) 2824 > COST(k,i) + COST(i,j), determine whether there exists 2825 another bi-neighbor u such that either COST(k,u) + COST(u,j) 2826 < COST(k,i) + COST(i,j), or COST(k,u) + COST(u,j) = COST(k,i) 2827 + COST(i,j) and either of the following conditions is true: 2829 o BNM(u,j) = 1, or 2830 o (SANM(j,u), SANM(u,j), RtrPri(u), MDR_Level(u), RID(u)) 2831 is lexicographically greater than 2832 (SANM(j,i), SANM(i,j), RtrPri(i), MDR_Level(i), RID(i)). 2834 If for some such bi-neighbor k, there does not exist such a 2835 bi-neighbor u, then set new_sel_adv(j) = 1. 2837 (6) For each MANET interface I, update the SANS to equal the set of 2838 all bi-neighbors j such that new_sel_adv(j) = 1 and I is the 2839 preferred interface for j. If LSAFullness = 2, the SANS SHOULD 2840 also include other bidirectional neighbors to provide redundant 2841 routes. 2843 (7) With the SANS updated, a new router-LSA may need to be 2844 originated as described in Section 9.2.3. 2846 The lexicographical comparison of Step 5e gives preference to links 2847 that are already advertised, in order to improve LSA stability. 2849 The above algorithm can be run in O(d^2) time if a single link change 2850 occurs. For example, if link (x,y) fails where x and y are neighbors 2851 of router i, and either SANS(x,y) = 1 or BNM(x,y) = 1, then Step 5 2852 need only be performed for pairs j, k such that either j or k is 2853 equal to x or y. 2855 D. Non-Ackable LSAs for Periodic Flooding 2857 In a highly mobile network, it is possible that a router almost 2858 always originates a new router-LSA every MinLSInterval seconds. In 2859 this case, it should not be necessary to send Acks for such an LSA, 2860 or to retransmit such an LSA as a unicast, or to describe such an LSA 2861 in a DD packet. In this case, the originator of an LSA MAY indicate 2862 that the router-LSA is "non-ackable" by setting the L bit in the 2863 options field of the LSA. For example, a router can originate non- 2864 ackable LSAs if it determines (e.g., based on an exponential moving 2865 average) that a new LSA is originated every MinLSInterval seconds at 2866 least 90 percent of the time. (Simulations are needed to determine 2867 the best threshold.) 2869 A non-ackable LSA is never acknowledged, nor is it ever retransmitted 2870 as a unicast or described in a DD packet, thus saving substantial 2871 overhead. However, the originating router must periodically 2872 retransmit the current instance of its router-LSA as a multicast 2873 (until it originates a new LSA, which will usually happen before the 2874 previous instance is retransmitted), and each MDR must periodically 2875 retransmit each non-ackable LSA as a multicast (until it receives a 2876 new instance of the LSA, which will usually happen before the 2877 previous instance is retransmitted). The retransmission interval 2878 should be slightly larger than MinLSInterval (e.g., MinLSInterval + 2879 1) so that a new instance of the LSA is usually received before the 2880 previous one is retransmitted. Note that the reception of a 2881 retransmitted (duplicate) LSA does not result in immediate forwarding 2882 of the LSA; only a new LSA (with a larger sequence number) may be 2883 forwarded immediately, according to the flooding procedure of Section 2884 8. 2886 Authors' Addresses 2888 Richard G. Ogier 2889 SRI International 2890 Email: rich.ogier@earthlink.net, richard.ogier@sri.com 2892 Phil Spagnolo 2893 Boeing Phantom Works 2894 Email: phillip.a.spagnolo@boeing.com 2896 Intellectual Property Statement 2898 The IETF takes no position regarding the validity or scope of any 2899 Intellectual Property Rights or other rights that might be claimed to 2900 pertain to the implementation or use of the technology described in 2901 this document or the extent to which any license under such rights 2902 might or might not be available; nor does it represent that it has 2903 made any independent effort to identify any such rights. Information 2904 on the procedures with respect to rights in RFC documents can be 2905 found in BCP 78 and BCP 79. 2907 Copies of IPR disclosures made to the IETF Secretariat and any 2908 assurances of licenses to be made available, or the result of an 2909 attempt made to obtain a general license or permission for the use of 2910 such proprietary rights by implementers or users of this 2911 specification can be obtained from the IETF on-line IPR repository at 2912 http://www.ietf.org/ipr. 2914 The IETF invites any interested party to bring to its attention any 2915 copyrights, patents or patent applications, or other proprietary 2916 rights that may cover technology that may be required to implement 2917 this standard. Please address the information to the IETF at ietf- 2918 ipr@ietf.org. 2920 Disclaimer of Validity 2922 This document and the information contained herein are provided on an 2923 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 2924 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 2925 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 2926 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 2927 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 2928 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 2930 Copyright Statement 2932 Copyright (C) The IETF Trust (2008). This document is subject to the 2933 rights, licenses and restrictions contained in BCP 78, and except as 2934 set forth therein, the authors retain all their rights. 2936 Acknowledgment 2938 Funding for the RFC Editor function is currently provided by the 2939 Internet Society.