idnits 2.17.1 draft-ietf-ospf-manet-mdr-01.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 3030. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 3007. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 3014. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 3020. 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 2482 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 (April 22, 2008) is 5847 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-04 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: October 2008 Boeing 6 April 22, 2008 8 MANET Extension of OSPF using CDS Flooding 9 draft-ietf-ospf-manet-mdr-01.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 Copyright Notice 35 Copyright (C) The IETF Trust (2008). 37 Abstract 39 This document specifies an extension of OSPF for IPv6 to support 40 mobile ad hoc networks (MANETs). The extension, called OSPF-MDR, is 41 designed as a new OSPF interface type for MANETs. OSPF-MDR is based 42 on the selection of a subset of MANET routers, consisting of MANET 43 Designated Routers (MDRs) and Backup MDRs. The MDRs form a connected 44 dominating set (CDS), and the MDRs and Backup MDRs together form a 45 biconnected CDS for robustness. This CDS is exploited in two ways. 46 First, to reduce flooding overhead, an optimized flooding procedure 47 is used in which only (Backup) MDRs flood new link state 48 advertisements (LSAs) back out the receiving interface; reliable 49 flooding is ensured by retransmitting LSAs along adjacencies. 50 Second, adjacencies are formed only between (Backup) MDRs and a 51 subset of their neighbors, allowing for much better scaling in dense 52 networks. The CDS is constructed using 2-hop neighbor information 53 provided in a Hello protocol extension. The Hello protocol is 54 further optimized by allowing differential Hellos that report only 55 changes in neighbor states. Options are specified for originating 56 router-LSAs that provide full or partial topology information, 57 allowing overhead to be reduced by advertising less topology 58 information. 60 Table of Contents 62 1 Introduction ................................................. 4 63 1.1 Terminology .................................................. 5 64 2 Overview ..................................................... 7 65 2.1 Selection of MDRs, BMDRs, Parents, and Adjacencies ........... 7 66 2.2 Flooding Procedure ........................................... 8 67 2.3 Link State Acknowledgments ................................... 9 68 2.4 Routable Neighbors ........................................... 9 69 2.5 Partial and Full Topology LSAs .............................. 10 70 2.6 Hello Protocol .............................................. 10 71 3 Interface and Neighbor Data Structures ...................... 11 72 3.1 Changes to Interface Data Structure ......................... 11 73 3.2 New Configurable Interface Parameters ....................... 12 74 3.3 Changes to Neighbor Data Structure .......................... 14 75 4 Hello Protocol .............................................. 15 76 4.1 Sending Hello Packets ....................................... 15 77 4.2 Receiving Hello Packets ..................................... 18 78 4.3 Neighbor Acceptance Condition ............................... 22 79 5 MDR Selection Algorithm ..................................... 22 80 5.1 Phase 1: Creating the Neighbor Connectivity Matrix .......... 24 81 5.2 Phase 2: MDR Selection ...................................... 25 82 5.3 Phase 3: Backup MDR Selection ............................... 26 83 5.4 Phase 4: Selection of the (Backup) Parent ................... 26 84 5.5 Phase 5: Optional Selection of Non-Flooding MDRs ............ 27 85 6 Interface State Machine ..................................... 28 86 6.1 Interface States ............................................ 28 87 6.2 Events that Cause Interface State Changes ................... 28 88 6.3 Changes to Interface State Machine .......................... 28 89 7 Adjacency Maintenance ....................................... 29 90 7.1 Changes to Neighbor State Machine ........................... 30 91 7.2 Whether to Become Adjacent .................................. 31 92 7.3 Whether to Eliminate an Adjacency ........................... 32 93 7.4 Sending Database Description Packets ........................ 32 94 7.5 Receiving Database Description Packets ...................... 32 95 8 Flooding Procedure .......................................... 33 96 8.1 LSA Forwarding Procedure .................................... 34 97 8.2 Sending Link State Acknowledgments .......................... 37 98 8.3 Retransmitting LSAs ......................................... 38 99 8.4 Receiving Link State Acknowledgments ........................ 38 100 9 Router-LSAs ................................................. 39 101 9.1 Routable Neighbors .......................................... 39 102 9.2 Backbone Neighbors .......................................... 40 103 9.3 Selected Advertised Neighbors ............................... 41 104 9.4 Originating Router-LSAs ..................................... 42 105 10 Calculating the Routing Table ............................... 43 106 11 Security Considerations ..................................... 44 107 12 IANA Considerations ......................................... 44 108 13 Acknowledgments ............................................. 44 109 14 Normative References ........................................ 44 110 15 Informative References ...................................... 44 111 A Packet Formats .............................................. 45 112 A.1 Options Field ............................................... 45 113 A.2 Link-Local Signaling ........................................ 45 114 A.3 Hello Packet DR and Backup DR Fields ........................ 49 115 A.4 LSA Formats and Examples .................................... 49 116 B Detailed Algorithms for MDR/BMDR Selection .................. 53 117 B.1 Detailed Algorithm for Step 2.4 (MDR Selection) ............. 53 118 B.2 Detailed Algorithm for Step 3.2 (BMDR Selection) ............ 54 119 C Min-Cost LSA Algorithm ...................................... 56 120 D Non-Ackable LSAs for Periodic Flooding ...................... 59 121 E Simulation Results .......................................... 59 122 Authors Addresses ........................................... 61 123 Intellectual Property and Copyright Statements .............. 62 125 1. Introduction 127 This document specifies an extension of OSPF for IPv6 [RFC2328, 128 RFC2740], to support a new interface type for mobile ad hoc networks 129 (MANETs), i.e., for broadcast-capable, multihop wireless networks in 130 which routers and hosts can be mobile. This extension is also 131 applicable to non-mobile mesh networks using layer-3 routing. 132 Existing OSPF interface types do not perform adequately in such 133 environments, due to scaling issues regarding the flooding protocol 134 operation, inability of the Designated Router election protocol to 135 converge in all scenarios, and large numbers of adjacencies when 136 using a Point-to-Multipoint interface type. 138 An OSPF implementation that is extended with this MANET interface 139 type does not preclude the use of any existing interface types, and 140 is fully compatible with a legacy OSPF implementation. MANET 141 networks are represented externally as Point-to-Multipoint networks, 142 although the design borrows concepts used by the OSPF broadcast 143 interface type. 145 The approach taken is to generalize the concept of an OSPF Designated 146 Router (DR) and Backup DR to multihop wireless networks, in order to 147 reduce overhead by reducing the number of routers that must flood new 148 LSAs and reducing the number of adjacencies. The generalized 149 (Backup) Designated Routers are called (Backup) MANET Designated 150 Routers (MDRs). The MDRs form a connected dominating set (CDS), and 151 the MDRs and Backup MDRs together form a biconnected CDS for 152 robustness. By definition, each router in the MANET either belongs 153 to the CDS or is one hop away from it. A distributed algorithm is 154 used to select and dynamically maintain the biconnected CDS. 155 Adjacencies are established only between (Backup) MDRs and a subset 156 of their neighbors, thus resulting in a dramatic reduction in the 157 number of adjacencies in dense networks, compared to the approach of 158 forming adjacencies between all neighbor pairs. The OSPF extension 159 is called OSPF-MDR. 161 Hello packets are modified, using OSPF link-local signaling [LLS], 162 for two purposes: to provide neighbors with 2-hop neighbor 163 information that is required by the MDR selection algorithm, and to 164 allow differential Hellos that report only changes in neighbor 165 states. Differential Hellos can be sent more frequently without a 166 significant increase in overhead, in order to respond more quickly to 167 topology changes. 169 Each MANET router advertises a subset of its MANET neighbors as 170 point-to-point links in its router-LSA. The choice of which 171 neighbors to advertise is flexible, allowing overhead to be reduced 172 by advertising less topology information. Options are specified for 173 originating router-LSAs that provide full or partial topology 174 information. 176 This document is organized as follows. Section 2 presents an overview 177 of OSPF-MDR, Section 3 presents the new interface and neighbor data 178 items that are required for the extension, Section 4 describes the 179 Hello protocol, including procedures for maintaining the 2-hop 180 neighbor information, Section 5 describes the MDR selection 181 algorithm, Section 6 describes changes to the Interface state 182 machine, section 7 describes the procedures for forming adjacencies 183 and deciding which neighbors should become adjacent, Section 8 184 describes the flooding procedure, Section 9 specifies the 185 requirements and options for the contents of router-LSAs, and Section 186 10 describes changes in the calculation of the routing table. 188 The appendix specifies packet formats, detailed algorithms for the 189 MDR selection algorithm, an algorithm for the selection of a subset 190 of neighbors to advertise in the router-LSA to provide shortest-path 191 routing, a proposed option that uses non-ackable LSAs to provide 192 periodic flooding without the overhead of Link State Acknowledgments, 193 and simulation results that predict the performance of OSPF-MDR in 194 mobile networks with up to 200 nodes. Additional information and 195 resources for OSPF-MDR can be found at http://www.manet-routing.org. 197 1.1. Terminology 199 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 200 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 201 document are to be interpreted as described in [RFC2119]. 203 In addition, this document uses the following terms: 205 MANET Interface 206 A new OSPF interface type that supports broadcast-capable, 207 multihop wireless networks. Two neighboring routers on a MANET 208 interface may not be able to communicate directly with each other. 209 A neighboring router on a MANET interface is called a MANET 210 neighbor. MANET neighbors are discovered dynamically using a 211 modification of OSPF's Hello protocol. 213 MANET Router 214 An OSPF router that has at least one MANET interface. 216 Differential Hello 217 A Hello packet that reduces the overhead of sending full Hellos, 218 by including only the Router IDs of neighbors whose state changed 219 recently. 221 2-Hop Neighbor Information 222 Information that specifies the bidirectional neighbors of each 223 neighbor. The modified Hello protocol provides each MANET router 224 with 2-hop neighbor information, which is used for selecting MDRs 225 and Backup MDRs. 227 MANET Designated Router (MDR) 228 One of a set of routers responsible for flooding new LSAs, and for 229 determining the set of adjacencies that must be formed. The set 230 of MDRs forms a connected dominating set and is a generalization 231 of the DR found in the broadcast network. 233 Backup MANET Designated Router (Backup MDR or BMDR) 234 One of a set of routers responsible for providing backup flooding 235 when neighboring MDRs fail. The set of MDRs and Backup MDRs forms 236 a biconnected dominating set. The Backup MDR is a generalization 237 of the Backup DR found in the broadcast network. 239 MDR Other 240 A router is an MDR Other for a particular MANET interface if it is 241 neither an MDR nor a Backup MDR for that interface. 243 Parent 244 Each router selects a Parent for each MANET interface. The Parent 245 of a non-MDR router will be a neighboring MDR if one exists. The 246 Parent of an MDR is always the router itself. Each non-MDR router 247 becomes adjacent with its Parent. The Router ID of the Parent is 248 advertised in the DR field of each Hello sent on the interface. 250 Backup Parent 251 If the option of biconnected adjacencies is chosen, then each MDR 252 Other selects a Backup Parent, which will be a neighboring MDR or 253 BMDR if one exists that is not the Parent. The Backup Parent of a 254 BMDR is always the router itself. Each MDR Other becomes adjacent 255 with its Backup Parent if it exists. The Router ID of the Backup 256 Parent is advertised in the Backup DR field of each Hello sent on 257 the interface. 259 Bidirectional Neighbor 260 A neighboring router whose neighbor state is 2-Way or greater. 261 The set of such neighbors is called the Bidirectional Neighbor Set 262 (BNS). 264 Routable Neighbor 265 A bidirectional MANET neighbor becomes routable if the SPF 266 calculation has produced a route to the neighbor and the neighbor 267 satisfies a quality condition. Once a neighbor becomes routable, 268 it remains routable as long as it remains bidirectional. Only 269 routable and Full neighbors can be used as next hops in the SPF 270 calculation, and can be included in the router-LSA originated by 271 the router. 273 Non-flooding MDR 274 An MDR that does not immediately flood received LSAs back out the 275 receiving interface. Some MDRs may declare themselves non- 276 flooding in order to reduce flooding overhead. 278 2. Overview 280 This section provides an overview of OSPF-MDR, including motivation 281 and rationale for some of the design choices. 283 OSPF-MDR was motivated by the desire to extend OSPF to support 284 MANETs, while keeping the same design philosophy as OSPF and using 285 techniques that are similar to those of OSPF. For example, OSPF 286 reduces overhead in a broadcast network by electing a Designated 287 Router (DR) and Backup DR, and by having two neighboring routers form 288 an adjacency only if one of them is the DR or Backup DR. This idea 289 can be generalized to a multihop wireless network by forming a 290 spanning tree, with the edges of the tree being the adjacencies and 291 the interior (non-leaf) nodes of the tree being the generalized DRs, 292 called MANET Designated Routers (MDRs). 294 To provide better robustness and fast response to topology changes, 295 it was decided that a router should decide whether it is an MDR based 296 only on local information that can be obtained from neighbors' 297 Hellos. The resulting set of adjacencies therefore does not always 298 form a tree globally, but appears to be a tree locally. Similarly, 299 the Backup DR can be generalized to Backup MDRs (BMDRs), to provide 300 robustness through biconnected redundancy. The set of MDRs forms a 301 connected dominating set (CDS), and the set of MDRs and BMDRs forms a 302 biconnected dominating set. 304 The following subsections provide an overview of each of the main 305 features of OSPF-MDR, starting with a summary of how MDRs, BMDRs, and 306 adjacencies are selected. 308 2.1. Selection of MDRs, BMDRs, Parents, and Adjacencies 310 The MDR selection algorithm is distributed; each router selects 311 itself as an MDR, BMDR, or other router (called an "MDR Other") based 312 on information about its one-hop neighborhood, which is obtained from 313 Hello packets received from neighbors. Routers are ordered 314 lexicographically based on the tuple (RtrPri, MDR Level, RID), where 315 RtrPri is the Router Priority, MDR Level represents the current state 316 of the router (2 for an MDR, 1 for a BMDR, and 0 for an MDR Other), 317 and RID is the Router ID. Routers with lexicographically larger 318 values of (RtrPri, MDR Level, RID) are given preference for becoming 319 MDRs. 321 The MDR selection algorithm can be summarized as follows. If the 322 router itself has a larger value of (RtrPri, MDR Level, RID) than all 323 of its neighbors, it selects itself as an MDR. Otherwise, let Rmax 324 denote the neighbor with the largest value of (RtrPri, MDR Level, 325 RID). The router then selects itself as an MDR unless each neighbor 326 can be reached from Rmax in at most k hops via neighbors that have a 327 larger value of (RtrPri, MDR Level, RID) than the router itself, 328 where k is the parameter MDRConstraint, whose default value is 3. 330 This parameter serves to control the density of the MDR set, since 331 the MDR set need not be strictly minimal. 333 Similarly, a router that does not select itself as an MDR will select 334 itself as a BMDR unless each neighbor can be reached from Rmax via 335 two node-disjoint paths, using as intermediate hops only neighbors 336 that have a larger value of (RtrPri, MDR Level, RID) than the router 337 itself. 339 When a router selects itself as an MDR, it also decides which MDR 340 neighbors it should become adjacent with, to ensure that the set of 341 MDRs and the adjacencies between them form a connected backbone. 342 Each non-MDR router selects and becomes adjacent with an MDR neighbor 343 called its parent, thus ensuring that all routers are connected to 344 the MDR backbone. 346 If the option of biconnected adjacencies is chosen (AdjConnectivity = 347 2), then additional adjacencies are selected to ensure that the set 348 of MDRs and BMDRs, and the adjacencies between them, form a 349 biconnected backbone. In this case, each MDR Other selects and 350 becomes adjacent with an MDR/BMDR neighbor called its backup parent, 351 in addition to its parent. 353 OSPF-MDR also provides the option of full-topology adjacencies 354 (AdjConnectivity = 0). If this option is selected, then each router 355 forms an adjacency with each bidirectional neighbor. 357 Prioritizing routers according to (RtrPri, MDR Level, RID) allows 358 neighboring routers to agree on which routers should become an MDR, 359 and gives higher priority to existing MDRs, which increases the 360 lifetime of MDRs and the adjacencies between them. In addition, 361 parents are selected to be existing adjacent neighbors whenever 362 possible, to avoid forming new adjacencies unless necessary. Once a 363 neighbor becomes adjacent, it remains adjacent as long as the 364 neighbor is bidirectional and either the neighbor or the router 365 itself is an MDR or BMDR (similar to OSPF). The above rules reduce 366 the rate at which new adjacencies are formed, which is important 367 since database exchange must be performed whenever a new adjacency is 368 formed. 370 2.2. Flooding Procedure 372 When an MDR receives a new LSA on a MANET interface, it immediately 373 floods the LSA back out the receiving interface unless it can be 374 determined that such flooding is unnecessary. When a Backup MDR 375 receives a new LSA on a MANET interface, it waits a short interval 376 (BackupWaitInterval), and then floods the LSA only if it has a 377 neighbor that did not flood or acknowledge the LSA and is not known 378 to be a neighbor of another neighbor (of the Backup MDR) that flooded 379 the LSA. 381 MDR Other routers never flood LSAs back out the receiving interface. 382 To exploit the broadcast nature of MANETs, a new LSA is processed 383 (and possibly forwarded) if it is received from any neighbor in state 384 2-Way or greater. The flooding procedure also avoids redundant 385 forwarding of LSAs when multiple interfaces exist. 387 2.3. Link State Acknowledgments 389 All Link State Acknowledgment packets are multicast. An LSA is 390 acknowledged if it is a new LSA, or if it is a duplicate LSA received 391 as a unicast. (A duplicate LSA received as multicast is not 392 acknowledged.) An LSA that is flooded back out the same interface is 393 treated as an implicit acknowledgment. Link state acknowledgments 394 may be delayed to allow coalescing multiple acknowlegments in the 395 same packet. The only exception is that (Backup) MDRs send a 396 multicast link state acknowledgment immediately when a duplicate LSA 397 is received as a unicast, in order to prevent additional 398 retransmissions. Only link state acknowledgments from adjacent 399 neighbors are processed, and retransmitted LSAs are sent (via 400 unicast) only to adjacent neighbors. 402 2.4. Routable Neighbors 404 In OSPF, a neighbor must typically be fully adjacent (in state Full) 405 for it to be used in the SPF calculation. An exception exists for an 406 OSPF broadcast network, to avoid requiring all pairs of routers in 407 such a network to form adjacencies, which would generate a large 408 amount of overhead. In such a network, a router can use a non- 409 adjacent neighbor as a next hop as long as both routers are fully 410 adjacent with the Designated Router. We define this neighbor 411 relationship as a "routable neighbor" and extend its usage to the 412 MANET interface type. 414 A MANET neighbor becomes routable if it is bidirectional and the SPF 415 calculation has produced a route to the neighbor. (A flexible 416 quality condition may also be required.) Only routable and Full 417 neighbors can be used as next hops in the SPF calculation, and can be 418 included in the router-LSA originated by the router. The idea is 419 that if the SPF calculation has produced a route to the neighbor, 420 then it makes sense to take a "shortcut" and forward packets directly 421 to the neighbor. 423 The routability condition is a generalization of the way that 424 neighbors on broadcast networks are treated in the SPF calculation. 425 The network-LSA of an OSPF broadcast network implies that a router 426 can use a non-adjacent neighbor as a next hop. But a network-LSA 427 cannot describe the general topology of a MANET, making it necessary 428 to explicitly include non-adjacent neighbors in the router-LSA. 429 Allowing only adjacent neighbors in LSAs would either result in 430 suboptimal routes or would require a large number of adjacencies. 432 2.5. Partial and Full Topology LSAs 434 OSPF-MDR allows routers to originate both full-topology LSAs, which 435 advertise links to all routable and Full neighbors, and partial- 436 topology LSAs, which advertise only a subset of such links. In a 437 dense network, partial-topology LSAs are typically much smaller than 438 full-topology LSAs, thus achieving better scalability. 440 Each router advertises a subset of its neighbors as point-to-point 441 connections in its router-LSA. The choice of which neighbors to 442 advertise is flexible. As a minimum requirement, each router must 443 advertise a minimum set of "backbone" neighbors in its router-LSA. 444 An LSA that includes only this minimum set of neighbors is called a 445 minimal LSA and corresponds to LSAFullness = 0. This choice results 446 in the minimum amount of LSA flooding overhead, but does not ensure 447 routing along shortest paths. However, it is useful for achieving 448 scalability to networks with a large number of nodes. 450 At the other extreme, if LSAFullness = 4, then the router originates 451 a full-topology LSA, which includes all routable and Full neighbors. 453 Setting LSAFullness to 1 results in min-cost LSAs, which provide 454 routing along shortest (minimum-cost) paths. Each router decides 455 which neighbors to include in its router-LSA based on 2-hop neighbor 456 information obtained from its neighbors' Hellos. Each router 457 includes in its LSA the minimum set of neighbors necessary to provide 458 a shortest path between each pair of its neighbors. 460 Setting LSAFullness to 3 results in MDR full LSAs, causing each MDR 461 to originate a full-topology LSA whle other routers originate minimal 462 LSAs. This choice does not provide routing along shortest paths, but 463 simulations have shown that it provides routing along nearly shortest 464 paths with relatively low overhead. 466 The above LSA options are interoperable with each other, because they 467 all require the router-LSA to include a minimum set of neighbors, and 468 because the construction of the router-LSA (described in Section 9.4) 469 ensures that the router-LSAs originated by different routers are 470 consistent. 472 2.6. Hello Protocol 474 OSPF-MDR uses the same Hello format as OSPFv3, but appends additional 475 information to Hello packets using link-local signaling (LLS), in 476 order to indicate the set of bidirectional neighbors and other 477 information that is used by the MDR selection algorithm and the min- 478 cost LSA algorithm. In addition to full Hellos, which include the 479 same set of neighbor IDs as OSPFv3 Hellos, OSPF-MDR allows the use of 480 differential Hellos, which include only the IDs of neighbors whose 481 state (or other information) has recently changed (within the last 482 HelloRepeatCount Hellos). 484 Differential Hellos are sent every HelloInterval seconds, except when 485 full Hellos are sent, which happens once every 2HopRefresh Hellos. 486 The default value of 2HopRefresh is 1, i.e., the default is to send 487 only full Hellos. The default value for HelloInterval is 2 seconds. 488 Differential Hellos are used to reduce overhead and to allow Hellos 489 to be sent more frequently, for faster reaction to topology changes. 491 3. Interface and Neighbor Data Structures 493 3.1. Changes to Interface Data Structure 495 The following modified or new data items are required for the 496 Interface Data Structure of a MANET interface: 498 Type 499 A router that implements this extension can have one or more 500 interfaces of type MANET, in addition to the OSPF interface types 501 defined in RFC 2328. 503 State 504 The possible states for a MANET interface are the same as for a 505 broadcast interface. However, the DR and Backup states now imply 506 that the router is an MDR or Backup MDR, respectively. 508 MDR Level 509 The MDR Level is equal to MDR (value 2) if the router is an MDR, 510 Backup MDR (value 1) if the router is a Backup MDR, and MDR Other 511 (value 0) otherwise. The MDR Level is used by the MDR selection 512 algorithm. 514 Parent 515 The Parent replaces the Designated Router (DR) data item of OSPF. 516 Each router selects a Parent as described in Section 5.4. The 517 Parent of an MDR is the router itself, and the Parent of a non-MDR 518 router will be a neighboring MDR, if one exists. The Parent is 519 initialized to 0.0.0.0, indicating the lack of a Parent. Each 520 router advertises the Router ID of its Parent in the DR field of 521 each Hello sent on the interface. 523 Backup Parent 524 The Backup Parent replaces the Backup Designated Router data item 525 of OSPF. The Backup Parent of a BMDR is the router itself. If 526 the option of biconnected adjacencies is chosen, then each MDR 527 Other selects a Backup Parent, which will be a neighboring 528 MDR/BMDR if one exists that is not the Parent. The Backup Parent 529 is initialized to 0.0.0.0, indicating the lack of a Backup Parent. 530 Each router advertises the Router ID of its Backup Parent in the 531 Backup DR field of each Hello sent on the interface. 533 Router Priority 534 An 8-bit unsigned integer. A router with a larger Router Priority 535 is more likely to be selected as an MDR. The Router Priority for 536 a MANET interface can be changed dynamically based on any 537 criteria, including bandwidth capacity, willingness to be a relay 538 (which can depend on battery life, for example), number of 539 neighbors (degree), and neighbor stability. A router that has 540 been a (Backup) MDR for a certain amount of time can reduce its 541 Router Priority so that the burden of being a (Backup) MDR can be 542 shared among all routers. If the Router Priority for a MANET 543 interface is changed, then the interface variable 544 MDRNeighborChange must be set. 546 Hello Sequence Number (HSN) 547 The 16-bit sequence number carried by the MDR-Hello TLV. The HSN 548 is incremented by 1 (modulo 2^16) every time a Hello packet is 549 sent on the interface. 551 MDRNeighborChange 552 A single-bit variable set to 1 if a neighbor change has occurred 553 that requires the MDR selection algorithm to be executed. 555 3.2. New Configurable Interface Parameters 557 The following new configurable interface parameters are required for 558 a MANET interface. The default values for HelloInterval, 559 RouterDeadInterval, and RxmtInterval for a MANET interface are 2, 6, 560 and 7 seconds, respectively. 562 The default configuration for OSPF-MDR uses uniconnected adjacencies 563 (AdjConnectivity = 1) and partial-topology LSAs that provide 564 shortest-path routing (LSAFullness = 1). This is the most scalable 565 configuration that provides shortest-path routing. Other 566 configurations may be preferable in special circumstances. For 567 example, setting LSAFullness to 4 provides full-topology LSAs, and 568 setting LSAFullness to 0 provides minimal LSAs that minimize overhead 569 but do not ensure shortest-path routing. Setting AdjConnectivity to 570 2 may improve robustness by providing a biconnected adjacency 571 subgraph, and setting AdjConnectivity to 0 results in full-topology 572 adjacencies. 574 Differential Hellos should be used to reduce the size of Hello 575 packets when the average number of neighbors is large. Differential 576 Hellos are obtained by setting the parameter 2HopRefesh to an integer 577 greater than 1, with the recommended value being 3. Good performance 578 in simulated mobile networks with up to 140 nodes has been obtained 579 using the default configuration with differential Hellos. Good 580 performance in simulated mobile networks with up to 200 nodes has 581 been obtained using the same configuration except with minimal LSAs 582 (LSAFullness = 0). Simulation results are presented in Appendix E. 584 Although all routers should preferably choose the same values for the 585 new configurable interface parameters, this is not required. OSPF- 586 MDR was carefully designed so that correct interoperation is achieved 587 even if each router sets these parameters independently of the other 588 routers. 590 AdjConnectivity 591 If equal to the default value of 1, then the set of adjacencies 592 forms a (uni)connected graph. If equal to the optional value of 2, 593 then the set of adjacencies forms a biconnected graph. If 594 AdjConnectivity is 0, then adjacency reduction is not used, i.e., 595 the router becomes adjacent with all of its neighbors. 597 MDRConstraint 598 A parameter of the MDR selection algorithm, which affects the 599 number of MDRs selected. The default value of 3 results in nearly 600 the minimum number of MDRs. The optional value 2 results in a 601 larger number of MDRs. 603 BackupWaitInterval 604 The number of seconds that a Backup MDR must wait after receiving 605 a new LSA, before it decides whether to flood the LSA. The 606 default value is 0.5 second. 608 LSAFullness 609 Determines which neighbors a router should advertise in its 610 router-LSA. The value 0 results in minimal LSAs that include only 611 "backbone" neighbors. The values 1 and 2 result in partial- 612 topology LSAs that provide shortest-path routing, with the value 2 613 providing redundant routes. The value 3 results in MDRs 614 originating full-topology LSAs and other routers originating 615 minimal LSAs. The value 4 results in all routers originating 616 full-topology LSAs. The default value is 1. 618 AckInterval 619 The interval between Link State Acknowledgment packets when only 620 delayed acknowledgments need to be sent. AckInterval MUST be less 621 than RxmtInterval, and SHOULD NOT be larger than 1 second. The 622 default value is 1 second. 624 2HopRefresh 625 One out of every 2HopRefresh Hellos sent on the interface must be 626 a full Hello. All other Hellos are differential. The default 627 value is 1, i.e., the default is to send only full Hellos. If 628 differential Hellos are used, the recommended value of 2HopRefresh 629 is 3. 631 HelloRepeatCount 632 The number of consecutive Hellos in which a neighbor must be 633 included when its state changes, if differential Hellos are used. 634 This parameter must be set to 3. 636 3.3. Changes to Neighbor Data Structure 638 The neighbor states are the same as for OSPF. However, the data for 639 a MANET neighbor that has transitioned to the Down state must be 640 maintained for at least HelloInterval * HelloRepeatCount seconds, to 641 allow the state change to be reported in differential Hellos. The 642 following new data items are required for the Neighbor Data Structure 643 of a neighbor on a MANET interface. 645 Neighbor Hello Sequence Number (NHSN) 646 The Hello sequence number contained in the last Hello received 647 from the neighbor. 649 A-bit 650 The A-bit copied from the MDR-Hello TLV of the last Hello received 651 from the neighbor. This bit is 1 if the neighbor is using full- 652 topology adjacencies, i.e., is not using adjacency reduction. 654 FullHelloRcvd 655 A single-bit variable equal to 1 if a full Hello has been received 656 from the neighbor. 658 Neighbor's MDR Level 659 The MDR Level of the neighbor, based on the DR and Backup DR 660 fields of the last Hello packet received from the neighbor or from 661 the MDR-DD TLV in a DD packet received from the neighbor. 663 Neighbor's Parent 664 The neighbor's choice for Parent, obtained from the DR field of 665 the last Hello packet received from the neighbor or from the MDR- 666 DD TLV in a DD packet received from the neighbor. 668 Neighbor's Backup Parent 669 The neighbor's choice for Backup Parent, obtained from the Backup 670 DR field of the last Hello packet received from the neighbor or 671 from the MDR-DD TLV in a DD packet received from the neighbor. 673 Child 674 A single-bit variable equal to 1 if the neighbor is a child, i.e., 675 if the neighbor has selected the router as a (Backup) Parent. 677 Dependent Neighbor 678 A single-bit variable equal to 1 if the neighbor is a Dependent 679 Neighbor, which is decided by the MDR selection algorithm. Each 680 MDR/BMDR router becomes adjacent with its Dependent Neighbors 681 (which are also MDR/BMDR routers) to form a connected backbone. 682 The set of all Dependent Neighbors is called the Dependent 683 Neighbor Set (DNS). 685 Dependent Selector 686 A single-bit variable equal to 1 if the neighbor has selected the 687 router to be Dependent. 689 Selected Advertised Neighbor (SAN) 690 A single-bit variable equal to 1 if the neighbor is a selected 691 advertised neighbor. The set of all Selected Advertised Neighbors 692 is called the Selected Advertised Neighbor Set (SANS). The SANS 693 consists of neighbors that the router has selected to be included 694 in the router-LSA, along with other neighbors that are required to 695 be included. 697 Routable 698 A single-bit variable equal to 1 if the neighbor is routable. 700 Neighbor's Bidirectional Neighbor Set (BNS) 701 The neighbor's set of bidirectional neighbors, which is updated 702 when a Hello is received from the neighbor. 704 Neighbor's Dependent Neighbor Set (DNS) 705 The neighbor's set of Dependent Neighbors, which is updated when a 706 Hello is received from the neighbor. 708 Neighbor's Selected Advertised Neighbor Set (SANS) 709 The neighbor's set of Selected Advertised Neighbors, which is 710 updated when a Hello is received from the neighbor. 712 Neighbor's Link Metrics 713 The link metric for each of the neighbor's bidirectional 714 neighbors, obtained from the Metric TLV appended to Hello packets. 716 4. Hello Protocol 718 The MANET interface utilizes Hellos for neighbor discovery and for 719 enabling neighbors to learn 2-hop neighbor information. The protocol 720 is flexible because it allows the use of full or differential Hellos. 721 Full Hellos list all neighbors in state Init or above, as in OSPFv3, 722 whereas differential Hellos list only neighbors whose status as a 723 bidirectional neighbor, Dependent Neighbor, or Selected Advertised 724 Neighbor has recently changed. Differential Hellos are used to 725 reduce overhead, and they allow Hellos to be sent more frequently 726 (for faster reaction to topology changes). If differential Hellos 727 are used, full Hellos are sent less frequently to ensure that all 728 neighbors have current 2-hop neighbor information. 730 4.1. Sending Hello Packets 732 Hello packets are sent according to [RFC2740] Section 3.2.1.1 and 733 [RFC2328] Section 9.5 with the following MANET specific 734 specifications beginning after paragraph 3 of Section 9.5. The Hello 735 packet format is defined in [RFC2740] A.3.2, except for the ordering 736 of the Neighbor IDs and the meaning of the DR and Backup DR fields as 737 described below. 739 Similar to [RFC2328], the DR and Backup DR fields indicate whether 740 the router is an MDR or Backup MDR. If the router is an MDR, then 741 the DR field is the router's own Router ID, and if the router is a 742 Backup MDR, then the Backup DR field is the router's own Router ID. 743 These fields are also used to advertise the router's Parent and 744 Backup Parent, as specified in Section A.3 and Section 5.4. 746 Hellos are sent every HelloInterval seconds. Full Hellos are sent 747 every 2HopRefresh Hellos, and differential Hellos are sent at all 748 other times. For example, if 2HopRefresh is equal to 3, then every 749 third Hello is a full Hello. If 2HopRefresh is set to 1, then all 750 Hellos are full (the default). 752 The neighbor IDs included in the body of each Hello are divided into 753 the following five disjoint lists of neighbors (some of which may be 754 empty), and must appear in the following order: 756 List 1. Neighbors whose state recently changed to Down (included 757 only in differential Hellos). 758 List 2. Neighbors in state Init. 759 List 3. Dependent Neighbors. 760 List 4. Selected Advertised Neighbors. 761 List 5. Unselected bidirectional neighbors, defined as bidirectional 762 neighbors that are neither Dependent nor Selected Advertised 763 Neighbors. 765 Note that all neighbors in Lists 3 through 5 are bidirectional 766 neighbors. These lists are used to update the neighbor's 767 Bidirectional Neighbor Set (BNS), Dependent Neighbor Set (DNS), and 768 Selected Advertised Neighbor Set (SANS) when a Hello is received. 770 Note that the above five lists are disjoint, so each neighbor can 771 appear in at most one list. Also note that some or all of the five 772 lists can be empty. 774 Link-local signaling (LLS) is used to append up to two TLVs to each 775 MANET Hello packet. The format for LLS is given in Section A.2. The 776 MDR-Hello TLV is appended to each (full or differential) MANET Hello 777 packet. It indicates whether the Hello is full or differential, and 778 gives the Hello Sequence Number (HSN) and the number of neighbor IDs 779 in each of Lists 1 through 4 defined above. The size of List 5 is 780 then implied by the packet length field of the Hello. The format of 781 the MDR-Hello TLV is given in Section A.2.3. 783 In both full and differential Hellos, the appended MDR-Hello TLV is 784 built as follows. 786 o The Sequence Number field is set to the current HSN for the 787 interface; the HSN is then incremented (modulo 2^16). 789 o The D-bit of the MDR-Hello TLV is set to 1 for a differential 790 Hello and 0 for a full Hello. 792 o The A-bit of the MDR-Hello TLV is set to 1 if AdjConnectivity is 0 793 (the router is using full-topology adjacencies); otherwise it is 794 set to 0. 796 o The N1, N2, N3, and N4 fields are set to the number of neighbor 797 IDs in the body of the Hello that are in List 1, List 2, List 3, 798 and List 4, respectively. (N1 is always zero in a full Hello.) 800 The MDR-Metric TLV (or Metric TLV) advertises the link cost to each 801 bidirectional neighbor on the interface, to allow the selection of 802 neighbors to include in partial-topology LSAs. If LSAFullness is 1 803 or 2, a Metric TLV must be appended to each MANET Hello packet unless 804 all link costs are 1. The format of the Metric TLV is given in 805 Section A.2.5. The I bit of the Metric TLV can be set to 0 or 1. If 806 the I bit is set to 0, then the Metric TLV does not contain neighbor 807 IDs, and contains the metric for each bidirectional neighbor listed 808 in the (full or differential) Hello, in the same order. If the I bit 809 is set to 1, then the Metric TLV includes the neighbor ID and metric 810 for each bidirectional neighbor listed in the Hello whose metric is 811 not equal to the Default Metric field of the TLV. 813 The I bit should be chosen to minimize the size of the Metric TLV. 814 This can be achieved by choosing the I bit to be 1 if and only if the 815 number of bidirectional neighbors listed in the Hello whose metric 816 differs from the Default Metric field is less than 1/3 of the total 817 number of bidirectional neighbors listed in the Hello. 819 For example, if all neighbors have the same metric, then the I bit 820 should be set to 1, with the Default Metric equal to this metric, 821 avoiding the need to include neighbor IDs and corresponding metrics 822 in the TLV. At the other extreme, if all neighbors have different 823 metrics, then the I bit should be set to 0 to avoid listing the same 824 neighbor IDs in both the body of the Hello and the Metric TLV. 826 In both full and differential Hello packets, the L bit is set in the 827 Hello's option field to indicate LLS. 829 4.1.1. Full Hello Packet 831 In a full Hello, the neighbor ID list includes all neighbors in state 832 Init or higher, in the order described above. The MDR-Hello TLV is 833 built as described above. If a Metric TLV is appended, it is built 834 as specified in Section A.2.5. 836 4.1.2. Differential Hello Packet 838 In a differential Hello, the five neighbor ID lists defined in 839 Section 4.1 are populated as follows: 841 List 1 includes each neighbor in state Down that has not yet been 842 included in HelloRepeatCount Hellos since transitioning to this 843 state. 845 List 2 includes each neighbor in state Init that has not yet been 846 included in HelloRepeatCount Hellos since transitioning to this 847 state. 849 List 3 includes each Dependent Neighbor that has not yet been 850 included in HelloRepeatCount Hellos since becoming a Dependent 851 Neighbor. 853 List 4 includes each Selected Advertised Neighbor that has not yet 854 been included in HelloRepeatCount Hellos since becoming a Selected 855 Advertised Neighbor. 857 List 5 includes each unselected bidirectional neighbor (defined in 858 Section 4.1) that has not yet been included in HelloRepeatCount 859 Hellos since becoming an unselected bidirectional neighbor. 861 In addition, a bidirectional neighbor must be included (in the 862 appropriate list) if the neighbor's BNS does not include the router 863 (indicating that the neighbor does not consider the router to be 864 bidirectional). 866 If a Metric TLV is appended to the Hello, then a bidirectional 867 neighbor must be included (in the appropriate list) if it has not yet 868 been included in HelloRepeatCount Hellos since its metric last 869 changed. 871 4.2. Receiving Hello Packets 873 A Hello packet received on a MANET interface is processed as 874 described in [RFC2740] Section 3.2.2.1 and the first two paragraphs 875 of [RFC2328] Section 10.5, followed by the processing specified 876 below. 878 The source of a received Hello packet is identified by the Router ID 879 found in the Hello's OSPF packet header. If a matching neighbor 880 cannot be found in the interface's data structure, one is created 881 with the Neighbor ID set to the Router ID found in the OSPF packet 882 header, the state initialized to Down, all MANET-specific neighbor 883 variables (specified in Section 3.3) initialized to zero, and the 884 neighbor's DNS, SANS, and BNS initialized to empty sets. 886 The neighbor structure's Router Priority is set to the value of the 887 corresponding field in the received Hello packet. The Neighbor's 888 Parent is set to the value of the DR field, and the Neighbor's Backup 889 Parent is set to the value of the Backup DR field. 891 Now the rest of the Hello Packet is examined, generating events to be 892 given to the neighbor and interface state machines. These state 893 machines are specified either to be executed or scheduled (see 894 [RFC2328] Section 4.4 "Tasking support"). For example, by specifying 895 below that the neighbor state machine be executed in line, several 896 neighbor state transitions may be affected by a single received 897 Hello. 899 o If the L bit in the options field is not set, then an error has 900 occurred and the Hello is discarded. 902 o If the LLS contains a MDR-Hello TLV, the neighbor state machine is 903 executed with the event HelloReceived. Otherwise, an error has 904 occurred and the Hello is discarded. 906 o The Hello Sequence Number and the A-bit in the MDR-Hello TLV are 907 copied to the neighbor's data structure. 909 o The DR and Backup DR fields are processed as follows. 911 (1) If the DR field is equal to the neighbor's Router ID, 912 set the neighbor's MDR Level to MDR. 914 (2) Else if the Backup DR field is equal to the neighbor's 915 Router ID, set the neighbor's MDR Level to Backup MDR. 917 (3) Else, set the neighbor's MDR Level to MDR Other and set the 918 neighbor's Dependent Neighbor variable to 0. (Only MDR/BMDR 919 neighbors can be Dependent.) 921 (4) If the DR or Backup DR field is equal to the router's own 922 Router ID, set the neighbor's Child variable to 1; otherwise 923 set it to 0. 925 The neighbor ID list of the Hello is divided as follows into the five 926 lists defined in Section 4.1, where N1, N2, N3, and N4 are obtained 927 from the corresponding fields of the MDR-Hello TLV. List 1 is 928 defined to be the first N1 neighbor IDs, List 2 is defined to be the 929 next N2 neighbor IDs, List 3 is defined to be the next N3 neighbor 930 IDs, List 4 is defined to be the next N4 neighbor IDs, and List 5 is 931 defined to be the remaining neighbor IDs in the Hello. 933 Further processing of the Hello depends on whether it is full or 934 differential, which is indicated by the value of the D-bit of the 935 MDR-Hello TLV. 937 4.2.1. Full Hello Packet 939 If the received Hello is full (the D-bit of the MDR-Hello TLV is 0), 940 the following steps are performed: 942 o If the N1 field of the MDR-Hello TLV is not zero, then an error 943 has occurred and the Hello is discarded. Otherwise, set 944 FullHelloRcvd to 1. 946 o In the neighbor structure, modify the neighbor's DNS to equal the 947 set of neighbor IDs in the Hello's List 3, modify the neighbor's 948 SANS to equal the set of neighbor IDs in the Hello's List 4, and 949 modify the neighbor's BNS to equal the set of neighbor IDs in the 950 union of Lists 3, 4, and 5. 952 o If the router itself appears in the Hello's neighbor ID list, the 953 neighbor state machine is executed with the event 2-WayReceived 954 after the Hello is processed. Otherwise, the neighbor state 955 machine is executed with the event 1-WayReceived after the Hello 956 is processed. 958 4.2.2. Differential Hello Packet 960 If the received Hello is differential (the D-bit of the MDR-Hello TLV 961 is 1), the following steps are performed: 963 (1) For each neighbor ID in List 1 or List 2 of the Hello: 965 o Remove the neighbor ID from the neighbor's DNS, SANS, 966 and BNS, if it belongs to the neighbor set. 968 (2) For each neighbor ID in List 3 of the Hello: 970 o Add the neighbor ID to the neighbor's DNS and BNS, if it 971 does not belong to the neighbor set. 973 o Remove the neighbor ID from the neighbor's SANS, if it 974 belongs to the neighbor set. 976 (3) For each neighbor ID in List 4 of the Hello: 978 o Add the neighbor ID to the neighbor's SANS and BNS, if it 979 does not belong to the neighbor set. 981 o Remove the neighbor ID from the neighbor's DNS, if it 982 belongs to the neighbor set. 984 (4) For each neighbor ID in List 5 of the Hello: 986 o Add the neighbor ID to the neighbor's BNS, if it does not 987 belong to the neighbor set. 989 o Remove the neighbor ID from the neighbor's DNS and SANS, if 990 it belongs to the neighbor set. 992 (5) If the router's own RID appears in List 1, execute the neighbor 993 state machine with the event 1-WayReceived after the Hello is 994 processed. 996 (6) If the router's own RID appears in List 2, 3, 4, or 5, execute 997 the neighbor state machine with the event 2-WayReceived after 998 the Hello is processed. 1000 (7) If the router's own RID does not appear in the Hello's neighbor 1001 ID list, and the neighbor state is 2-Way or greater, and the 1002 Hello Sequence Number is less than or equal to the previous 1003 sequence number plus HelloRepeatCount, then the neighbor state 1004 machine is executed with the event 2-WayReceived after the Hello 1005 is processed (the state does not change). 1007 (8) If 2-WayReceived is not executed, then 1-WayReceived is executed 1008 after the Hello is processed. 1010 4.2.3. Additional Processing for Both Hello Types 1012 The following applies to both full and differential Hellos. 1014 If the router itself belongs to the neighbor's DNS, the neighbor's 1015 Dependent Selector variable is set to 1; otherwise it is set to 0. 1017 The receiving interface's MDRNeighborChange variable is set to 1 if 1018 any of the following changes occurred as a result of processing the 1019 Hello: 1021 o The neighbor's state changed from less than 2-Way to 2-Way or 1022 greater, or vice versa. 1024 o The neighbor is bidirectional and any of the following neighbor 1025 variables has changed: MDR Level, Router Priority, FullHelloRcvd, 1026 and Bidirected Neighbor Set (BNS). 1028 The neighbor state machine is scheduled with the event AdjOK? if any 1029 of the following changes occurred as a result of processing the 1030 Hello: 1032 o The neighbor's state changed from less than 2-Way to 2-Way or 1033 greater. 1035 o The neighbor is bidirectional and its MDR Level has changed, or 1036 its Child variable or Dependent Selector variable has changed from 1037 0 to 1. 1039 If the LLS contains a Metric TLV, it is processed by updating the 1040 neighbor's link metrics according to the format of the Metric TLV 1041 specified in Section A.2.5. If the LLS does not contain a Metric TLV 1042 and LSAFullness is 1 or 2, the metric for each of the neighbor's 1043 links is set to 1. 1045 4.3. Neighbor Acceptance Condition 1047 In wireless networks, a single Hello can be received from a neighbor 1048 with which a poor connection exists, e.g., because the neighbor is 1049 almost out of range. To avoid accepting poor quality neighbors, and 1050 to employ hysteresis, a router may require that a stricter condition 1051 be satisfied before changing the state of a MANET neighbor from Down 1052 to Init or greater. This condition is called the "neighbor 1053 acceptance condition", which by default is the reception of a single 1054 Hello or DD packet. For example, the neighbor acceptance condition 1055 may require that 2 consecutive Hellos be received from a neighbor 1056 before changing the neighbor's state from Down to Init. Other 1057 possible conditions include the reception of 3 consecutive Hellos, or 1058 the reception of 2 of the last 3 Hellos. The neighbor acceptance 1059 condition may also impose thresholds on other measurements such as 1060 received signal strength. 1062 The neighbor state transition for state Down and event HelloReceived 1063 is thus modified (see Section 7.1) to depend on the neighbor 1064 acceptance condition. 1066 5. MDR Selection Algorithm 1068 This section describes the MDR selection algorithm, which determines 1069 whether the router is an MDR, Backup MDR, or MDR Other on a given 1070 interface. The algorithm also selects the Dependent Neighbors and 1071 the (Backup) Parent, which are used to decide which neighbors should 1072 become adjacent (see Section 7.2). 1074 The MDR selection algorithm must be executed just before sending a 1075 Hello if the MDRNeighborChange bit is set for the interface. The 1076 algorithm SHOULD also be executed whenever a bidirectional neighbor 1077 transitions to less than 2-Way, and MAY be executed at other times 1078 when the MDRNeighborChange bit is set. The bit is cleared after the 1079 algorithm is executed. 1081 To simplify the implementation, the MDR selection algorithm MAY be 1082 executed periodically just before sending each Hello, to avoid having 1083 to determine when the MDRNeighborChange bit should be set. After 1084 running the MDR selection algorithm, the AdjOK? event may be invoked 1085 for some or all neighbors as specified in Section 7. 1087 The purpose of the MDRs is to provide a minimal set of relays for 1088 flooding LSAs, and the purpose of the Backup MDRs is to provide 1089 backup relays to flood LSAs when flooding by MDRs does not succeed. 1091 The set of MDRs forms a CDS, and the set of MDRs and Backup MDRs 1092 forms a biconnected CDS. 1094 Each MDR selects and becomes adjacent with a subset of its MDR 1095 neighbors, called Dependent Neighbors, forming a connected backbone. 1096 Each non-MDR router connects to this backbone by selecting and 1097 becoming adjacent with an MDR neighbor called its Parent. Each MDR 1098 selects itself as Parent, to inform neighbors that it is an MDR. 1100 If AdjConnectivity = 2, then each (Backup) MDR selects and becomes 1101 adjacent with additional (Backup) MDR neighbors to form a biconnected 1102 backbone, and each MDR Other selects and becomes adjacent with a 1103 second (Backup) MDR neighbor called its Backup Parent, thus becoming 1104 connected to the backbone via two adjacencies. Each BMDR selects 1105 itself as Backup Parent, to inform neighbors that it is a BMDR. 1107 The MDR selection algorithm is a distributed CDS algorithm that uses 1108 2-hop neighbor information obtained from Hellos. More specifically, 1109 it uses as inputs the set of bidirectional neighbors (in state 2-Way 1110 or greater), the triplet (Router Priority, MDR Level, Router ID) for 1111 each such neighbor and for the router itself, and the neighbor 1112 variables Bidirectional Neighbor Set (BNS) and FullHelloRcvd for each 1113 such neighbor. The MDR selection algorithm can be implemented in 1114 O(d^2) time, where d is the number of neighbors. 1116 The above triplet will be abbreviated as (RtrPri, MDR Level, RID). 1117 The triplet (RtrPri, MDR Level, RID) is said to be larger for Router 1118 A than for Router B if the triplet for Router A is lexicographically 1119 greater than the triplet for Router B. Routers that have larger 1120 values of this triplet are preferred for selection as an MDR. The 1121 algorithm therefore prefers routers that are already MDRs, resulting 1122 in a longer average MDR lifetime. 1124 The MDR selection algorithm consists of five phases, the last of 1125 which is optional. Phase 1 creates the neighbor connectivity matrix, 1126 which determines which pairs of neighbors are neighbors of each 1127 other. Phase 2 decides whether the calculating router is an MDR, and 1128 which MDR neighbors are Dependent. Phase 3 decides whether the 1129 calculating router is a Backup MDR and, if AdjConnectivity = 2, which 1130 additional MDR/BMDR neighbors are Dependent. Phase 4 selects the 1131 Parent and Backup Parent. 1133 The algorithm simplifies considerably if AdjConnectivity is 0 (full- 1134 topology adjacencies). In this case, the set of Dependent Neighbors 1135 is empty and MDR Other routers need not select parents. Also, Phase 1136 3 (BMDR selection) is not required if AdjConnectivity is 0 or 1. 1137 However, Phase 3 MUST be executed if AdjConnectivity is 2, and SHOULD 1138 be executed if AdjConnectivity is 0 or 1, since BMDRs improve 1139 robustness by providing backup flooding. 1141 A router that has selected itself as an MDR in Phase 2 MAY execute 1142 Phase 5 to possibly declare itself a non-flooding MDR. A non- 1143 flooding MDR is the same as a flooding MDR except that it does not 1144 immediately flood received LSAs back out the receiving interface, 1145 because it has determined that neighboring MDRs exist that will 1146 ensure all neighbors are covered. Instead, a non-flooding MDR 1147 performs backup flooding just like a BMDR. A non-flooding MDR 1148 maintains its MDR level (rather than being demoted to a BMDR) in 1149 order to maximize the stability of adjacencies. (The decision to 1150 form an adjacency does not depend on whether an MDR is non-flooding.) 1151 By having MDRs declare themselves to be non-flooding when possible, 1152 flooding overhead is reduced. The resulting reduction in flooding 1153 overhead can be dramatic for certain regular topologies, but has been 1154 found to be less than 15% for random topologies. 1156 For convenience, in the following description, the term "bi-neighbor" 1157 will be used as an abbreviation for "bidirectional neighbor". 1159 5.1. Phase 1: Creating the Neighbor Connectivity Matrix 1161 The neighbor connectivity matrix (NCM) assigns a value of 0 or 1 for 1162 each pair of bi-neighbors, depending on the Bidirectional Neighbor 1163 Set (BNS) and the value of FullHelloRcvd for each neighbor. NCM is a 1164 symmetric matrix that defines a topology graph for the set of bi- 1165 neighbors. A value of 1 for a given pair of neighbors indicates that 1166 the neighbors are assumed to be bi-neighbors of each other in the MDR 1167 selection algorithm. Letting i denote the router itself, NCM(i,j) 1168 and NCM(j,i) are set to 1 for each bi-neighbor j. The value of the 1169 matrix is set as follows for each pair of bi-neighbors j and k. 1171 (1.1) If FullHelloRcvd is 1 for both neighbors j and k: NCM(j,k) = 1172 NCM(k,j) is 1 only if j belongs to the BNS of neighbor k and k 1173 belongs to the BNS of neighbor j. 1175 (1.2) If FullHelloRcvd is 1 for neighbor j and is 0 for neighbor k: 1176 NCM(j,k) = NCM(k,j) is 1 only if k belongs to the BNS of 1177 neighbor j. 1179 (1.3) If FullHelloRcvd is 0 for both neighbors j and k: NCM(j,k) = 1180 NCM(k,j) = 0. 1182 In step 1.1 above, two neighbors are considered to be bi-neighbors of 1183 each other only if they both agree that the other router is a bi- 1184 neighbor. This provides faster response to the failure of a link 1185 between two neighbors, since it is likely that one router will detect 1186 the failure before the other router. In step 1.2 above, only neighbor 1187 j has reported its full BNS, so neighbor j is believed in deciding 1188 whether j and k are bi-neighbors of each other. As Step 1.3 1189 indicates, two neighbors are assumed not to be bi-neighbors of each 1190 other if neither neighbor has reported its full BNS. 1192 5.2. Phase 2: MDR Selection 1194 Phase 2 depends on the parameter MDRConstraint, which affects the 1195 number of MDRs selected. The default value of 3 results in nearly the 1196 minimum number of MDRs, while the value 2 results in a larger number 1197 of MDRs. If AdjConnectivity = 0 (full-topology adjacencies), then 1198 the following steps are modified in that Dependent Neighbors are not 1199 selected. 1201 (2.1) The set of Dependent Neighbors is initialized to be empty. 1203 (2.2) If the router has a larger value of (RtrPri, MDR Level, RID) 1204 than all of its bi-neighbors, the router selects itself as an 1205 MDR; selects all of its MDR bi-neighbors as Dependent 1206 Neighbors; if AdjConnectivity = 2, selects all of its BMDR bi- 1207 neighbors as Dependent Neighbors; then proceeds to Phase 4. 1209 (2.3) Let Rmax be the bi-neighbor with the largest value of (RtrPri, 1210 MDR Level, RID). 1212 (2.4) Using NCM to determine the connectivity of bi-neighbors, 1213 compute the minimum number of hops, denoted hops(u), from Rmax 1214 to each other bi-neighbor u, using only intermediate nodes that 1215 are bi-neighbors with a larger value of (RtrPri, MDR Level, 1216 RID) than the router itself. If no such path from Rmax to u 1217 exists, then hops(u) equals infinity. (See Appendix B for a 1218 detailed algorithm using breadth-first search.) 1220 (2.5) If hops(u) is at most MDRConstraint for each bi-neighbor u, the 1221 router selects no Dependent Neighbors, and sets its MDR Level 1222 as follows: If the MDR Level is currently MDR, then it is 1223 changed to BMDR if Phase 3 will be executed and to MDR Other if 1224 Phase 3 will not be executed. Otherwise, the MDR Level is not 1225 changed. 1227 (2.6) Else, the router sets its MDR Level to MDR and selects the 1228 following neighbors as Dependent Neighbors: Rmax if it is an 1229 MDR or BMDR; each MDR bi-neighbor u such that hops(u) is 1230 greater than MDRConstraint; and if AdjConnectivity = 2, each 1231 BMDR bi-neighbor u such that hops(u) is greater than 1232 MDRConstraint. 1234 (2.7) If steps 2.1 through 2.6 resulted in the MDR Level changing to 1235 BMDR, or to MDR with AdjConnectivity equal to 1 or 2, then 1236 execute steps 2.1 through 2.6 again. (This is necessary 1237 because the change in MDR Level can cause the set of Dependent 1238 Neighbors and the BFS tree to change.) This step is not 1239 required if the MDR selection algorithm is executed 1240 periodically. 1242 Step 2.4 can be implemented using a breadth-first search (BFS) 1243 algorithm to compute min-hop paths from Rmax to all other bi- 1244 neighbors, modified to allow a bi-neighbor to be an intermediate node 1245 only if its value of (RtrPri, MDR Level, RID) is larger than that of 1246 the router itself. A detailed description of this algorithm, which 1247 runs in O(d^2) time, is given in Appendix B. 1249 5.3. Phase 3: Backup MDR Selection 1251 (3.1) If the MDR Level is MDR (after running Phase 2) and 1252 AdjConnectivity is not 2, then proceed to Phase 4. (If the MDR 1253 Level is MDR and AdjConnectivity = 2, then Phase 3 may select 1254 additional Dependent Neighbors to create a biconnected 1255 backbone.) 1257 (3.2) Using NCM to determine the connectivity of bi-neighbors, 1258 determine whether or not there exist two node-disjoint paths 1259 from Rmax to each other bi-neighbor u, using only intermediate 1260 nodes that are bi-neighbors with a larger value of (RtrPri, MDR 1261 Level, RID) than the router itself. (See Appendix B for a 1262 detailed algorithm.) 1264 (3.3) If there exist two such node-disjoint paths from Rmax to each 1265 other bi-neighbor u, then the router selects no additional 1266 Dependent Neighbors and sets its MDR Level to MDR Other. 1268 (3.4) Else, the router sets its MDR Level to Backup MDR unless it 1269 already selected itself as an MDR in Phase 2, and if 1270 AdjConnectivity = 2, adds each of the following neighbors to 1271 the set of Dependent Neighbors: Rmax if it is an MDR or BMDR, 1272 and each MDR/BMDR bi-neighbor u such that step 3.2 did not find 1273 two node-disjoint paths from Rmax to u. 1275 (3.5) If steps 3.1 through 3.4 resulted in the MDR Level changing 1276 from MDR Other to BMDR, then run Phases 2 and 3 again. (This 1277 is necessary because running Phase 2 again can cause the MDR 1278 Level to change to MDR.) This step is not required if the MDR 1279 selection algorithm is executed periodically. 1281 Step 3.2 can be implemented in O(d^2) time using the algorithm given 1282 in Appendix B. A simplified version of the algorithm is also 1283 specified, which results in a larger number of BMDRs. 1285 5.4. Phase 4: Selection of the (Backup) Parent 1287 Each router selects a Parent for each MANET interface. The Parent of 1288 a non-MDR router will be a neighboring MDR if one exists. If the 1289 option of biconnected adjacencies is chosen, then each MDR Other 1290 selects a Backup Parent, which will be a neighboring MDR/BMDR if one 1291 exists that is not the Parent. The Parent of an MDR is always the 1292 router itself, and the Backup Parent of a BMDR is always the router 1293 itself. 1295 The (Backup) Parent is advertised in the (Backup) DR field of each 1296 Hello sent on the interface. As specified in Section 7.2, each 1297 router forms an adjacency with its Parent and Backup Parent if it 1298 exists and is a neighboring MDR/BMDR. 1300 For a given MANET interface, let Rmax denote the router with the 1301 largest value of (RtrPri, MDR Level, RID) among all bidirectional 1302 neighbors, if such a neighbor exists that has a larger value of 1303 (RtrPri, MDR Level, RID) than the router itself. Otherwise, Rmax is 1304 null. 1306 If the calculating router has selected itself as an MDR, then the 1307 Parent is equal to the router itself, and the Backup Parent is Rmax. 1308 (The latter design choice was made because it results in slightly 1309 better performance than choosing no Backup Parent.) If the router 1310 has selected itself as a BMDR, then the Backup Parent is equal to the 1311 router itself. 1313 If the router is a BMDR or MDR Other, the Parent is selected to be 1314 any adjacent neighbor that is an MDR, if such a neighbor exists. If 1315 no adjacent MDR neighbor exists, then the Parent is selected to be 1316 Rmax. By giving preference to neighbors that are already adjacent, 1317 the formation of a new adjacency is avoided when possible. Note that 1318 the Parent can be a non-MDR neighbor temporarily when no MDR neighbor 1319 exists. (This design choice was also made for performance reasons.) 1321 If AdjConnectivity = 2 and the calculating router is an MDR Other, 1322 then the Backup Parent is selected to be any adjacent neighbor that 1323 is an MDR or BMDR, other than the selected Parent, if such a neighbor 1324 exists. If no such neighbor exists, then the Backup Parent is 1325 selected to be the bidirectional neighbor, excluding the selected 1326 Parent, with the largest value of (RtrPri, MDR Level, RID). 1328 5.5. Phase 5: Optional Selection of Non-Flooding MDRs 1330 A router that has selected itself as an MDR MAY execute the following 1331 steps to possibly declare itself a non-flooding MDR. An MDR that 1332 does not execute the following steps is by default a flooding MDR. 1334 (5.1) If the router has a larger value of (RtrPri, MDR Level, RID) 1335 than all of its bi-neighbors, the router is a flooding MDR. Else, 1336 proceed to Step 5.2. 1338 (5.2) Let Rmax be the bi-neighbor that has the largest value of 1339 (RtrPri, MDR Level, RID). 1341 (5.3) Using NCM to determine the connectivity of bi-neighbors, 1342 compute the minimum number of hops, denoted hops(u), from Rmax to 1343 each other bi-neighbor u, using only intermediate nodes that are MDR 1344 bi-neighbors with a smaller value of (RtrPri, RID) than the router 1345 itself. (This can be done using BFS as in Step 2.4). 1347 (5.4) If hops(u) is at most MDRConstraint for each bi-neighbor u, 1348 then the router is a non-flooding MDR. Else, it is a flooding MDR. 1350 6. Interface State Machine 1352 6.1. Interface States 1354 No new states are defined for a MANET interface. However, the DR and 1355 Backup states now imply that the router is an MDR or Backup MDR, 1356 respectively. The following modified definitions apply to MANET 1357 interfaces: 1359 Waiting 1360 In this state, the router learns neighbor information from the 1361 Hello packets it receives, but is not allowed to run the MDR 1362 selection algorithm until it transitions out of the Waiting state 1363 (when the Wait Timer expires). This prevents unnecessary changes 1364 in the MDR selection resulting from incomplete neighbor 1365 information. The length of the Wait Timer is 2HopRefresh * 1366 HelloInterval seconds (the interval between full Hellos). 1368 DR Other 1369 The router has run the MDR selection algorithm and determined that 1370 it is not an MDR or a Backup MDR. 1372 Backup 1373 The router has selected itself as a Backup MDR. 1375 DR 1376 The router has selected itself as an MDR. 1378 6.2. Events that Cause Interface State Changes 1380 All interface events defined in RFC 2328, Section 9.2 apply to MANET 1381 interfaces, except for BackupSeen and NeighborChange. BackupSeen is 1382 never invoked for a MANET interface (since seeing a Backup MDR does 1383 not imply that the router itself cannot also be an MDR or Backup 1384 MDR). 1386 The event NeighborChange is replaced with the new interface variable 1387 MDRNeighborChange, which indicates that the MDR selection algorithm 1388 must be executed due to a change in neighbor information (see Section 1389 4.2.3). 1391 6.3. Changes to Interface State Machine 1393 This section describes the changes to the interface state machine for 1394 a MANET interface. The two state transitions specified below are for 1395 state-event pairs that are described in RFC 2328, but have modified 1396 action descriptions because MDRs are selected instead of DRs. The 1397 state transition in RFC 2328 for the event NeighborChange is omitted; 1398 instead the new interface variable MDRNeighborChange is used to 1399 indicate when the MDR selection algorithm needs to be executed. The 1400 state transition for the event BackupSeen does not apply to MANET 1401 interfaces, since this event is never invoked for a MANET interface. 1402 The interface state transitions for the events Loopback and UnloopInd 1403 are unchanged from RFC 2328. 1405 State: Down 1406 Event: InterfaceUp 1407 New state: Depends on action routine. 1409 Action: Start the interval Hello Timer, enabling the periodic 1410 sending of Hello packets out the interface. If the router 1411 is not eligible to become an MDR (Router Priority is 0), 1412 the state transitions to DR Other. Otherwise, the state 1413 transitions to Waiting and the single shot Wait Timer is 1414 started. 1416 State: Waiting 1417 Event: WaitTimer 1418 New state: Depends on action routine. 1420 Action: Run the MDR selection algorithm, which may result in a 1421 change to the router's MDR Level, Dependent Neighbors, 1422 and (Backup) Parent. As a result of this calculation, 1423 the new interface state will be DR Other, Backup, or DR. 1424 As a result of these changes, the AdjOK? neighbor event 1425 may be invoked for some or all neighbors. (See 1426 Section 7.) 1428 7. Adjacency Maintenance 1430 Adjacency forming and eliminating on non-MANET interfaces remain 1431 unchanged. Adjacency maintenance on a MANET interface requires 1432 changes to transitions in the neighbor state machine ([RFC2328] 1433 Section 10.3), to deciding whether to become adjacent ([RFC2328] 1434 Section 10.4), sending of DD packets ([RFC2328] Section 10.8), and 1435 receiving of DD packets ([RFC2328] Section 10.6). The specification 1436 below relates to the MANET interface only. 1438 If full-topology adjacencies are used (AdjConnectivity = 0), the 1439 router forms an adjacency with each bidirectional neighbor. If 1440 adjacency reduction is used (AdjConnectivity is 1 or 2), the router 1441 forms adjacencies with a subset of its neighbors, according to the 1442 rules specified in Section 7.2. 1444 An adjacency maintenance decision is made when any of the following 1445 four events occur between a router and its neighbor. The decision is 1446 made by executing the neighbor event AdjOK?. 1448 (1) The neighbor state changes from Init to 2-Way. 1449 (2) The MDR Level changes for the neighbor or for the router itself. 1450 (3) The neighbor is selected to be the (Backup) Parent. 1451 (4) The neighbor selects the router to be its (Backup) Parent. 1453 7.1. Changes to Neighbor State Machine 1455 The following specifies new transitions in the neighbor state 1456 machine. 1458 State(s): Down 1459 Event: HelloReceived 1460 New state: Depends on action routine. 1462 Action: If the neighbor acceptance condition is satisfied (see 1463 Section 4.3), the neighbor state transitions to Init and 1464 the Inactivity Timer is started. Otherwise, the neighbor 1465 remains in the Down state. 1467 State(s): Init 1468 Event: 2-WayReceived 1469 New state: 2-Way 1471 Action: Transition to neighbor state 2-Way. 1473 State(s): 2-Way 1474 Event: AdjOK? 1475 New state: Depends on action routine. 1477 Action: Determine whether an adjacency should be formed with the 1478 neighboring router (see Section 7.2). If not, the 1479 neighbor state remains at 2-Way and no further action is 1480 taken. 1482 Otherwise, the neighbor state changes to ExStart, and the 1483 following actions are performed. If the neighbor has a 1484 larger Router ID than the router's own ID, and the 1485 received packet is a DD packet with the initialize (I), 1486 more (M), and master (MS) bits set, then execute the 1487 event NegotiationDone, which causes the state to 1488 transition to Exchange. 1490 Otherwise (negotiation is not complete), the router 1491 increments the DD sequence number in the neighbor data 1492 structure. If this is the first time that an adjacency 1493 has been attempted, the DD sequence number should be 1494 assigned a unique value (like the time of day clock). It 1495 then declares itself master (sets the master/slave bit to 1496 master), and starts sending Database Description Packets, 1497 with the initialize (I), more (M) and master (MS) bits 1498 set, the MDR-DD TLV included in an LLS, and the L bit 1499 set. This Database Description Packet should be 1500 otherwise empty. This Database Description Packet should 1501 be retransmitted at intervals of RxmtInterval until the 1502 next state is entered (see [RFC2328] Section 10.8). 1504 State(s): ExStart or greater 1505 Event: AdjOK? 1506 New state: Depends on action routine. 1508 Action: Determine whether the neighboring router should still be 1509 adjacent (see Section 7.3). If yes, there is no state 1510 change and no further action is necessary. Otherwise, 1511 the (possibly partially formed) adjacency must be 1512 destroyed. The neighbor state transitions to 2-Way. The 1513 Link state retransmission list, Database summary list, 1514 and Link state request list are cleared of LSAs. 1516 7.2. Whether to Become Adjacent 1518 The following defines the method to determine if an adjacency should 1519 be formed between neighbors in state 2-Way. The following procedure 1520 does not depend on whether AdjConnectivity is 1 or 2, but the 1521 selection of Dependent Neighbors (by the MDR selection algorithm) 1522 depends on AdjConnectivity. 1524 If adjacency reduction is not used (AdjConnectivity = 0), then an 1525 adjacency is formed with each neighbor in state 2-Way. Otherwise an 1526 adjacency is formed with a neighbor in state 2-Way if any of the 1527 following conditions is true: 1529 (1) The router is a (Backup) MDR and the neighbor is a (Backup) 1530 MDR and is either a Dependent Neighbor or a Dependent Selector. 1532 (2) The neighbor is a (Backup) MDR and is the router's (Backup) 1533 Parent. 1535 (3) The router is a (Backup) MDR and the neighbor is a child. 1537 (4) The neighbor's A-bit is 1, indicating the neighbor is using 1538 full-topology adjacencies. 1540 Otherwise, an adjacency is not established and the neighbor remains 1541 in state 2-Way. 1543 7.3. Whether to Eliminate an Adjacency 1545 The following defines the method to determine if an existing 1546 adjacency should be eliminated. An existing adjacency is maintained 1547 if any of the following is true: 1549 (1) The router is an MDR or Backup MDR. 1551 (2) The neighbor is an MDR or Backup MDR. 1553 (3) The neighbor's A-bit is 1, indicating the neighbor is using 1554 full-topology adjacencies. 1556 Otherwise, the adjacency MAY be eliminated. 1558 7.4 Sending Database Description Packets 1560 Sending a DD packet on a MANET interface is the same as [RFC2740] 1561 Section 3.2.1.2 and [RFC2328] Section 10.8 with the following 1562 additions to paragraph 3 of Section 10.8. 1564 If the neighbor state is ExStart, the standard initialization packet 1565 is sent with an MDR-DD TLV appended using LLS, and the L bit is set 1566 in the DD packet's option field. The format for the MDR-DD TLV is 1567 specified in Section A.2.4. The DR and Backup DR fields of the MDR- 1568 DD TLV are set exactly the same as the DR and Backup DR fields of a 1569 Hello sent on the same interface. 1571 7.5. Receiving Database Description Packets 1573 Processing a DD packet received on a MANET interface is the same as 1574 [RFC2328] Section 10.6, except for the changes described in this 1575 section. The following additional steps are performed before 1576 processing the packet based on neighbor state in paragraph 3 of 1577 Section 10.6. 1579 o If the DD packet's L bit is set in the options field and an MDR-DD 1580 TLV is appended, then the MDR-DD TLV is processed as follows. 1582 (1) If the DR field is equal to the neighbor's Router ID: 1583 (a) Set the MDR Level of the neighbor to MDR. 1584 (b) Set the neighbor's Dependent Selector variable to 1. 1586 (2) Else if the Backup DR field is equal to the neighbor's 1587 Router ID: 1588 (a) Set the MDR Level of the neighbor to Backup MDR. 1589 (b) Set the neighbor's Dependent Selector variable to 1. 1591 (3) Else: 1592 (a) Set the MDR Level of the neighbor to MDR Other. 1593 (b) Set the neighbor's Dependent Selector variable to 0. 1595 (c) Set the neighbor's Dependent Neighbor variable to 0. 1597 (4) If the DR or Backup DR field is equal to the router's own 1598 Router ID, set the neighbor's Child variable to 1; otherwise 1599 set it to 0. 1601 o If the neighbor state is Init, the neighbor event 2-WayReceived is 1602 executed. 1604 o If the MDR Level of the neighbor changed, the neighbor state 1605 machine is scheduled with the event AdjOK?. 1607 o If the neighbor's Child status has changed from 0 to 1, the 1608 neighbor state machine is scheduled with the event AdjOK?. 1610 o If the neighbor's neighbor state changed from less than 2-Way to 1611 2-Way or greater, the neighbor state machine is scheduled with the 1612 event AdjOK?. 1614 In addition, if the router accepts a received DD packet and processes 1615 its contents, then the following action SHOULD be performed for each 1616 LSA listed in the DD packet (whether the router is master or slave). 1617 If the router has an instance of the LSA in the Database summary list 1618 for the neighbor, which is the same or less recent than the LSA 1619 listed in the packet, then the LSA is removed from the Database 1620 summary list. This avoids including the LSA in a DD packet sent to 1621 the neighbor, when the neighbor already has an instance of the LSA 1622 that is the same or more recent. This optimization reduces overhead 1623 due to DD packets by approximately 50% in large networks. 1625 8. Flooding Procedure 1627 This section specifies the changes to RFC 2328, Section 13 for 1628 routers that support OSPF-MDR. The first part of Section 13 (before 1629 Section 13.1) is the same except for the following three changes. 1631 o To exploit the broadcast nature of MANETs, if the Link State 1632 Update (LSU) packet was received on a MANET interface, then the 1633 packet is dropped without further processing only if the sending 1634 neighbor is in a lesser state than 2-Way. Otherwise, the LSU 1635 packet is processed as described in this section. 1637 o If the received LSA is the same instance as the database copy, the 1638 following actions are performed in addition to step 7. For each 1639 MANET interface for which a BackupWait Neighbor List exists for 1640 the LSA (see Section 8.1): 1642 (a) Remove the sending neighbor from the BackupWait Neighbor List 1643 if it belongs to the list. 1644 (b) For each neighbor on the receiving interface that belongs 1645 to the BNS for the sending neighbor, remove the neighbor 1646 from the BackupWait Neighbor List if it belongs to the list. 1648 o Step 8, which handles the case in which the database copy of the 1649 LSA is more recent than the received LSA, is modified as follows. 1650 If the sending neighbor is in a lesser state than Exchange, then 1651 the router does not send the LSA back to the sending neighbor. 1653 There are no changes to Sections 13.1, 13.2, or 13.4. The following 1654 subsections describe the changes to Sections 13.3 (Next step in the 1655 flooding procedure), 13.5 (Sending Link State Acknowledgments), 13.6 1656 (Retransmitting LSAs), and 13.7 (Receiving Link State 1657 Acknowledgments) of RFC 2328. 1659 8.1. LSA Forwarding Procedure 1661 Step 1 of [RFC2328], Section 13.3 should be performed, with the 1662 following change, so that the new LSA is placed on the Link State 1663 retransmission list for each appropriate adjacent neighbor. Step 1c 1664 is replaced with the following action, so that the LSA is not placed 1665 on the retransmission list for a neighbor that has already 1666 acknowledged the LSA. 1668 o If the new LSA was received from this neighbor, or a link state 1669 acknowledgment (LS Ack) for the new LSA has already been received 1670 from this neighbor, examine the next neighbor. 1672 To determine whether an Ack for the new LSA has been received from 1673 the neighbor, the router maintains an Acked LSA List for each 1674 adjacent neighbor, as described in Section 8.4. When a new LSA is 1675 received, the Acked LSA List for each neighbor, on each MANET 1676 interface, should be updated by removing any LS Ack that is for an 1677 older instance of the LSA than the one received. 1679 The following description will use the notion of a "covered" 1680 neighbor. A neighbor k is defined to be covered if the LSA was sent 1681 as a multicast by a MANET neighbor j, and neighbor k belongs to the 1682 Bidirectional Neighbor Set (BNS) for neighbor j. A neighbor k is 1683 also defined to be covered if the LSA was sent to the multicast 1684 address AllSPFRouters by a neighbor j on a broadcast interface on 1685 which both j and k are neighbors. (Note that j must be the DR or 1686 Backup DR for the broadcast network, since only these routers may 1687 send LSAs to AllSPFRouters on a broadcast network.) 1689 Steps 2 through 5 of [RFC2328], Section 13.3 are unchanged if the 1690 outgoing interface (on which the LSA may be forwarded) is not of type 1691 MANET. If the outgoing interface is of type MANET, then steps 2 1692 through 5 are replaced with the following steps, to determine whether 1693 the LSA should be forwarded on each eligible MANET interface. 1695 (2) If either of the following two conditions is satisfied for every 1696 bidirectional neighbor on the interface, examine the next 1697 interface (the LSA is not flooded out this interface). 1699 (a) The LSA or an Ack for the LSA has been received from the 1700 neighbor (over any interface). 1702 (b) The LSA was received on a MANET or broadcast interface, and 1703 the neighbor is covered (defined above). 1705 Note that the above two conditions do not assume the outgoing 1706 interface is the same as the receiving interface. 1708 (3) If the LSA was received on this interface, and the router is an 1709 MDR Other for this interface, examine the next interface (the LSA 1710 is not flooded out this interface). 1712 (4) If the LSA was received on this interface, and the router is a 1713 Backup MDR or a non-flooding MDR for this interface, then the 1714 router waits BackupWaitInterval before deciding whether to flood 1715 the LSA. To accomplish this, the router creates a BackupWait 1716 Neighbor List for the LSA, which initially includes every 1717 bidirectional neighbor on this interface that does not satisfy 1718 either of the conditions (a) and (b) in step 2. A single shot 1719 BackupWait Timer associated with the LSA is started, which is set 1720 to expire after BackupWaitInterval seconds plus a small amount of 1721 random jitter. (The actions performed when the BackupWait Timer 1722 expires are described below in Section 8.1.2.) Examine the next 1723 interface (the LSA is not immediately flooded out this 1724 interface). 1726 (5) If the router is a flooding MDR for this interface, or if the LSA 1727 was originated by the router itself, then the LSA is flooded out 1728 the interface (whether or not the LSA was received on this 1729 interface). The LSA is included in an LSU packet which is 1730 multicast out the interface using the destination IP address 1731 AllSPFRouters. 1733 (6) If the LSA was received on a MANET or broadcast interface that is 1734 different from this (outgoing) interface, then the following two 1735 steps SHOULD be performed to avoid redundant flooding. 1737 (a) If the router has a larger value of (RtrPri, MDR Level, RID) 1738 on the outgoing interface than every covered neighbor 1739 (defined above) that is a neighbor on BOTH the receiving and 1740 outgoing interfaces (or if no such neighbor exists), then the 1741 LSA is flooded out the interface. 1743 (b) Else, the router waits BackupWaitInterval before deciding 1744 whether to flood the LSA on the interface, by performing the 1745 actions in step 4 for a Backup MDR (whether or not the router 1746 is a Backup MDR on this interface). A separate BackupWait 1747 Neighbor List is created for each interface, but only one 1748 BackupWait Timer is associated with the LSA. Examine the 1749 next interface (the LSA is not immediately flooded out this 1750 interface). 1752 (7) If the optional step 6 is not performed, then the LSA is flooded 1753 out the interface. The LSA is included in an LSU packet which is 1754 multicast out the interface using the destination IP address 1755 AllSPFRouters. 1757 8.1.1. Note on Step 6 of LSA Forwarding Procedure 1759 Performing the optional Step 6 can greatly reduce flooding overhead 1760 if the LSA was received on a MANET or broadcast interface. For 1761 example, assume the LSA was received from the DR of a broadcast 1762 network that includes 100 routers, and 50 of the routers (not 1763 including the DR) are also attached to a MANET. Assume that these 50 1764 routers are neighbors of each other in the MANET, and that each has a 1765 neighbor in the MANET that is not attached to the broadcast network 1766 (and is therefore not covered). Then by performing Step 6 of the LSA 1767 forwarding procedure, the number of routers that forward the LSA from 1768 the broadcast network to the MANET is reduced from 50 to just 1 1769 (assuming that at most one of the 50 routers is an MDR). 1771 8.1.2. BackupWait Timer Expiration 1773 If the BackupWait Timer for an LSA expires, then the following steps 1774 are performed for each (MANET) interface for which a BackupWait 1775 Neighbor List exists for the LSA. 1777 (1) If the BackupWait Neighbor List for the interface contains at 1778 least one router that is currently a bidirectional neighbor, the 1779 following actions are performed. 1781 (a) The LSA is flooded out the interface. 1783 (b) If the LSA is on the Ack List for the interface (i.e., is 1784 scheduled to be included in a delayed Link State 1785 Acknowledgment packet), then the router SHOULD remove the LSA 1786 from the Ack List, since the flooded LSA will be treated as 1787 an implicit Ack. 1789 (c) If the LSA is on the Link State retransmission list for any 1790 neighbor, the retransmission SHOULD be rescheduled to occur 1791 after RxmtInterval seconds. 1793 (2) The BackupWait Neighbor List is then deleted (whether or not the 1794 LSA is flooded). 1796 8.2. Sending Link State Acknowledgments 1798 This section describes the procedure for sending Link State 1799 Acknowledgments (LS Acks) on MANET interfaces. Section 13.5 of RFC 1800 2328 remains unchanged for non-MANET interfaces, but does not apply 1801 to MANET interfaces. To minimize overhead due to LS Acks, and to 1802 take advantage of the broadcast nature of MANETs, all LS Ack packets 1803 sent on a MANET interface are multicast using the IP address 1804 AllSPFRouters. In addition, duplicate LSAs received as a multicast 1805 are not acknowledged. 1807 When a router receives an LSA, it must decide whether to send a 1808 delayed Ack, an immediate Ack, or no Ack. The interface parameter 1809 AckInterval is the interval between LS Ack packets when only delayed 1810 Acks need to be sent. A delayed Ack SHOULD be delayed by at least 1811 (RxmtInterval - AckInterval - 0.5) seconds and at most (RxmtInterval 1812 - 0.5) seconds after the LSA instance being acknowledged was first 1813 received. If AckInterval and RxmtInterval are equal to their default 1814 values of 1 and 7 seconds, respectively, this reduces Ack traffic by 1815 increasing the chance that a new instance of the LSA will be received 1816 before the delayed Ack is sent. An immediate Ack is sent immediately 1817 in a multicast LS Ack packet, which may also include delayed Acks 1818 that were scheduled to be sent. 1820 The decision whether to send a delayed or immediate Ack depends on 1821 whether the received LSA is new (i.e., is more recent than the 1822 database copy) or a duplicate (the same instance as the database 1823 copy), and on whether the LSA was received as a multicast or a 1824 unicast (which indicates a retransmitted LSA). The following rules 1825 are used to make this decision. 1827 (1) If the received LSA is new, a delayed Ack is sent on each 1828 MANET interface associated with the area, unless the LSA is 1829 flooded out the interface. 1831 (2) If the LSA is a duplicate and was received as a multicast, 1832 the LSA is not acknowledged. 1834 (3) If the LSA is a duplicate and was received as a unicast: 1836 (a) If the router is an MDR, or AdjConnectivity = 2 and the 1837 router is a Backup MDR, or AdjConnectivity = 0, then an 1838 immediate Ack is sent out the receiving interface. 1840 (b) Otherwise, a delayed Ack is sent out the receiving 1841 interface. 1843 The reason that (Backup) MDRs send an immediate Ack when a 1844 retransmitted LSA is received, is to try to prevent other adjacent 1845 neighbors from retransmitting the LSA, since (Backup) MDRs usually 1846 have a large number of adjacent neighbors. MDR Other routers do not 1847 send an immediate Ack (unless AdjConnectivity = 0) because they have 1848 fewer adjacent neighbors, and so the potential benefit does not 1849 justify the additional overhead resulting from sending immediate 1850 Acks. 1852 8.3. Retransmitting LSAs 1854 LSAs are retransmitted according to Section 13.6 of RFC 2328. Thus, 1855 LSAs are retransmitted only to adjacent routers. Therefore, since 1856 OSPF-MDR does not allow an adjacency to be formed between two MDR 1857 Other routers, an MDR Other never retransmits an LSA to another MDR 1858 Other, only to its parents, which are (Backup) MDRs. 1860 Retransmitted LSAs are included in LSU packets that are sent directly 1861 to an adjacent neighbor that did not acknowledge the LSA (explicitly 1862 or implicitly). The length of time between retransmissions is given 1863 by the configurable interface parameter RxmtInterval, whose default 1864 is 7 seconds for a MANET interface. To reduce overhead, several 1865 retransmitted LSAs should be included in a single LSU packet whenever 1866 possible. 1868 8.4. Receiving Link State Acknowledgments 1870 A Link State Acknowledgment (LS Ack) packet that is received from an 1871 adjacent neighbor (in state Exchange or greater) is processed as 1872 described in Section 13.7 of RFC 2328, with the additional steps 1873 described in this section. An LS Ack packet that is received from a 1874 neighbor in a lesser state than Exchange is discarded. 1876 Each router maintains an Acked LSA List for each adjacent neighbor, 1877 to keep track of any LSA instances the neighbor has acknowledged, but 1878 which the router itself has NOT yet received. This is necessary 1879 because (unlike RFC 2328) each router acknowledges an LSA only the 1880 first time it is received as a multicast. 1882 If the neighbor from which the LS Ack packet was received is in state 1883 Exchange or greater, then the following steps are performed for each 1884 LS Ack in the received LS Ack packet: 1886 (1) If the router does not have a database copy of the LSA being 1887 acknowledged, or has a database copy that is less recent than the 1888 one being acknowledged, the LS Ack is added to the Acked LSA List 1889 for the sending neighbor. 1891 (2) If the router has a database copy of the LSA being acknowledged, 1892 which is the same as the instance being acknowledged, then the 1893 following action is performed. For each MANET interface for which 1894 a BackupWait Neighbor List exists for the LSA (see Section 8.1), 1895 remove the sending neighbor from the BackupWait Neighbor List if 1896 it belongs to the list. 1898 9. Router-LSAs 1900 Unlike the DR of an OSPF broadcast network, an MDR does not originate 1901 a network-LSA, since a network-LSA cannot be used to describe the 1902 general topology of a MANET. Instead, each router advertises a 1903 subset of its MANET neighbors as point-to-point links in its router- 1904 LSA. The choice of which MANET neighbors to include in the router- 1905 LSA is flexible. Whether or not adjacency reduction is used, the 1906 router can originate either partial-topology or full-topology LSAs. 1908 If adjacency reduction is used (AdjConnectivity is 1 or 2), then as a 1909 minimum requirement each router must advertise a minimum set of 1910 "backbone" neighbors in its router-LSA. This minimum choice 1911 corresponds to LSAFullness = 0, and results in the minimum amount of 1912 LSA flooding overhead, but does not provide routing along shortest 1913 paths. 1915 Therefore, to allow routers to calculate shortest paths, without 1916 requiring every pair of neighboring routers along the shortest paths 1917 to be adjacent (which would be inefficient due to requiring a large 1918 number of adjacencies), a router-LSA may also advertise non-adjacent 1919 neighbors that satisfy a synchronization condition described below. 1921 To motivate this, we note that OSPF already allows a non-adjacent 1922 neighbor to be a next hop, if both the router and the neighbor belong 1923 to the same broadcast network (and are both adjacent to the DR). A 1924 network-LSA for a broadcast network (which includes all routers 1925 attached to the network) implies that any router attached to the 1926 network can forward packets directly to any other router attached to 1927 the network (which is why the distance from the network to all 1928 attached routers is zero in the graph representing the link-state 1929 database). 1931 Since a network-LSA cannot be used to describe the general topology 1932 of a MANET, the only way to advertise non-adjacent neighbors that can 1933 be used as next hops, is to include them in the router-LSA. However, 1934 to ensure that such neighbors are sufficiently synchronized, only 1935 "routable" neighbors are allowed to be included in LSAs, and to be 1936 used as next hops in the SPF calculation. 1938 9.1. Routable Neighbors 1940 If adjacency reduction is used, a bidirectional MANET neighbor 1941 becomes routable if the SPF calculation has found a route to the 1942 neighbor and the neighbor satisfies the routable neighbor quality 1943 condition (defined below). Since only routable and Full neighbors 1944 are advertised in router-LSAs, and since adjacencies are selected to 1945 form a connected spanning subgraph, this definition implies that 1946 there exists, or recently existed, a path of full adjacencies from 1947 the router to the routable neighbor. The idea is that, since a 1948 routable neighbor can be reached through an acceptable path, it makes 1949 sense to take a "shortcut" and forward packets directly to the 1950 routable neighbor. 1952 This requirement does not guarantee perfect synchronization, but 1953 simulations have shown that it performs well in mobile networks. 1954 This requirement avoids, for example, forwarding packets to a new 1955 neighbor that is poorly synchronized because it was not reachable 1956 before it became a neighbor. 1958 To avoid selecting poor quality neighbors as routable neighbors, a 1959 neighbor that is selected as a routable neighbor must satisfy the 1960 routable neighbor quality condition. By default, this condition is 1961 that the neighbor's BNS must include the router itself (indicating 1962 that the neighbor agrees the connection is bidirectional). 1963 Optionally, a router may impose a stricter condition. For example, a 1964 router may require that two Hellos have been received from the 1965 neighbor that (explicitly or implicitly) indicate that the neighbor's 1966 BNS includes the router itself. 1968 The single-bit neighbor variable Routable indicates whether the 1969 neighbor is routable, and is initially set to 0. If adjacency 1970 reduction is used, Routable is updated as follows when the state of 1971 the neighbor changes, or the SPF calculation finds a route to the 1972 neighbor, or a Hello is received that affects the routable neighbor 1973 quality condition. 1975 (1) If Routable is 0 for the neighbor, the state of the neighbor is 1976 2-Way or greater, there exists a route to the neighbor, and the 1977 routable neighbor quality condition (defined above) is satisfied, 1978 then Routable is set to 1 for the neighbor. 1980 (2) If Routable is 1 for the neighbor and the state of the neighbor 1981 is less than 2-Way, Routable is set to 0 for the neighbor. 1983 If adjacency reduction is not used (AdjConnectivity = 0), then 1984 routable neighbors are not computed and the set of routable neighbors 1985 remains empty. 1987 9.2. Backbone Neighbors 1989 The flexible choice for the router-LSA is made possible by defining 1990 two types of neighbors that are included in the router-LSA: backbone 1991 neighbors and selected advertised neighbors. 1993 If adjacency reduction is used, a bidirectional neighbor is defined 1994 to be a backbone neighbor if and only if it satisfies the condition 1995 for becoming adjacent (see Section 7.2). If adjacency reduction is 1996 not used (AdjConnectivity = 0), a bidirectional neighbor is a 1997 backbone neighbor if and only if the neighbor's A-bit is 0 1998 (indicating the neighbor is using adjacency reduction). This 1999 definition allows the interoperation between routers that use 2000 adjacency reduction and routers that do not. 2002 If adjacency reduction is used, then a router MUST include in its 2003 router-LSA all Full neighbors and all routable backbone neighbors. A 2004 minimal LSA, corresponding to LSAFullness = 0, includes only these 2005 neighbors. This choice guarantees connectivity, but does not ensure 2006 shortest paths. However, this choice is useful in large networks to 2007 achieve maximum scalability. 2009 9.3. Selected Advertised Neighbors 2011 To allow flexibility while ensuring that router-LSAs are symmetric 2012 (i.e., router i advertises a link to router j if and only if router j 2013 advertises a link to router i), each router maintains a selected 2014 advertised neighbor set (SANS), which consists of MANET neighbors 2015 that the router has selected to advertise in its router-LSA, not 2016 including backbone neighbors. Since the SANS does not include 2017 backbone neighbors (and thus Dependent Neighbors), the SANS and DNS 2018 are disjoint. Both of these neighbor sets are advertised in Hellos. 2020 If LSAFullness = 0 (minimal LSAs), then the SANS is empty. At the 2021 other extreme, if LSAFullness = 4 (full-topology LSAs), the SANS 2022 includes all bidirectional MANET neighbors except backbone neighbors. 2023 In between these two extremes, a router that is using adjacency 2024 reduction may select any subset of bidirectional non-backbone 2025 neighbors as its SANS. The resulting router-LSA is constructed as 2026 specified in Section 9.4. 2028 Since a router that is not using adjacency reduction typically has no 2029 backbone neighbors (unless it has neighbors that are using adjacency 2030 reduction), to ensure connectivity, such a router must choose its 2031 SANS to contain the SANS corresponding to LSAFullness = 1. For 2032 example, a router that is not using adjacency reduction can select 2033 LSAFullness to be 1 or 4. 2035 If LSAFullness is 1, the router originates min-cost LSAs, which are 2036 partial-topology LSAs that (when flooded) provide each router with 2037 sufficient information to calculate a shortest (minimum-cost) path to 2038 each destination. Appendix C describes the algorithm for selecting 2039 the neighbors to include in the SANS that results in min-cost LSAs. 2040 The input to this algorithm includes information obtained from Hellos 2041 received from each MANET neighbor, including the Bidirectional 2042 Neighbor Set (BNS), Dependent Neighbor Set (DNS), Selected Advertised 2043 Neighbor Set (SANS), and the Metric TLV. The Metric TLV, specified 2044 in Section A.2.5, is appended to each Hello (unless all link costs 2045 are 1) to advertise the link cost to each bidirectional neighbor. 2047 If LSAFullness is 2, the SANS must be selected to be a superset of 2048 the SANS corresponding to LSAFullness = 1. This choice provides 2049 shortest-path routing while allowing the router to advertise 2050 additional neighbors to provide redundant routes. 2052 If LSAFullness is 3, each MDR originates a full-topology LSA (which 2053 includes all Full and routable neighbors), while each non-MDR router 2054 originates a minimal LSA. If the router has multiple MANET 2055 interfaces, the router-LSA includes all Full and routable neighbors 2056 on each interface for which it is an MDR, and advertises only Full 2057 neighbors and routable backbone neighbors on its other interfaces. 2058 This choice provides routing along nearly shortest paths with 2059 relatively low overhead. 2061 Although this document specifies a few choices of the SANS, which 2062 correspond to different values of LSAFullness, it is important to 2063 note that other choices are possible. In addition, it is not 2064 necessary for different routers to choose the same value of 2065 LSAFullness. The different choices are interoperable because they 2066 all require the router-LSA to include a minimum set of neighbors, and 2067 because the construction of the router-LSA (described below) ensures 2068 that the router-LSAs originated by different routers are consistent. 2070 9.4. Originating Router-LSAs 2072 When a new router-LSA is originated, it includes a point-to-point 2073 (type 1) link for each MANET neighbor that is advertised. The set of 2074 neighbors to be advertised is determined as follows. If adjacency 2075 reduction is used, the router advertises all Full neighbors, and 2076 advertises each routable neighbor that satisfies any of the following 2077 three conditions. If adjacency reduction is not used 2078 (AdjConnectivity = 0), the router advertises each Full neighbor that 2079 satisfies any of the following three conditions. 2081 (1) The router's SANS (for any interface) includes j. 2083 (2) Neighbor j's SANS includes the router (to ensure symmetry). 2085 (3) Neighbor j is a backbone neighbor. 2087 Note that backbone neighbors and neighbors in the SANS need not be 2088 routable or Full, but only routable and Full neighbors may be 2089 included in the router-LSA. This is done so that the SANS, which is 2090 advertised in Hellos, does not depend on routability. 2092 A new router-LSA must be originated whenever a change in the set of 2093 routable, backbone, selected advertised, or Full neighbors causes 2094 either of the following two conditions to occur: 2096 o There exists a MANET neighbor j that satisfies the above 2097 conditions for inclusion in the router-LSA, but is not included in 2098 the current router-LSA. 2100 o The current router-LSA includes a MANET neighbor that is no longer 2101 bidirectional. 2103 The above conditions may be checked periodically just before sending 2104 each Hello, instead of checking them every time one of the neighbor 2105 sets changes. The following implementation was found to work well. 2106 Just before sending each Hello, and whenever a bidirectional neighbor 2107 transitions to less than 2-Way, the router runs the MDR selection 2108 algorithm, updates its adjacencies, routable neighbors, and selected 2109 advertised neighbors, then checks the above conditions to see if a 2110 new router-LSA should be originated. In addition, if a neighbor 2111 becomes bidirectional or Full, the router updates its routable 2112 neighbors and checks the above conditions. 2114 10. Calculating the Routing Table 2116 The routing table calculation is the same as specified in RFC 2328, 2117 except for the following changes to Section 16.1 (Calculating the 2118 shortest-path tree for an area). If full-topology adjacencies and 2119 full-topology LSAs are used (AdjConnectivity = 0 and LSAFullness = 2120 4), there is no change to Section 16.1. 2122 If adjacency reduction is used (AdjConnectivity is 1 or 2), then 2123 Section 16.1 is modified as follows. Recall from Section 9 that a 2124 router can use any routable neighbor as a next hop to a destination, 2125 whether or not the neighbor is advertised in the router-LSA. This is 2126 accomplished by modifying step 2 so that the router-LSA associated 2127 with the root vertex is replaced with a dummy router-LSA that 2128 includes links to all Full neighbors and all routable MANET 2129 neighbors. In addition, step 2b (checking for a link from W back to 2130 V) MUST be skipped when V is the root vertex and W is a routable 2131 MANET neighbor. However, Step 2b must still be executed when V is 2132 not the root vertex, to ensure compatibility with OSPFv3. 2134 If full-topology adjacencies and partial-topology LSAs are used, then 2135 Section 16.1 is modified as follows. Step 2 is modified so that the 2136 router-LSA associated with the root vertex is replaced with a dummy 2137 router-LSA that includes links to all Full neighbors. In addition, 2138 step 2b MUST be skipped when V is the root vertex and W is a Full 2139 MANET neighbor. (This is necessary since the neighbor's router-LSA 2140 need not contain a link back to the router.) 2142 If adjacency reduction is used with partial-topology LSAs, then the 2143 set of routable neighbors can change without causing the contents of 2144 the router-LSA to change. This could happen, for example, if a 2145 routable neighbor that was not included in the router-LSA transitions 2146 to the Down or Init state. Therefore, if the set of routable 2147 neighbors changes, the shortest-path tree must be recalculated even 2148 if the router-LSA does not change. 2150 After the shortest-path tree and routing table are calculated, the 2151 set of routable neighbors must be updated, since a route to a non- 2152 routable neighbor may have been discovered. If the set of routable 2153 neighbors changes, then the shortest-path tree and routing table must 2154 be calculated a second time. The second calculation will not change 2155 the set of routable neighbors again, so two calculations are 2156 sufficient. If the set of routable neighbors is updated periodically 2157 every HelloInterval seconds, then it is not necessary to update the 2158 set of routable neighbors immediately after the routing table is 2159 updated. 2161 11. Security Considerations 2163 This document proposes an extension of OSPFv3 and can use the same 2164 IPv6 security mechanisms as OSPFv3. Hence, this document does not 2165 raise any new security concerns. 2167 12. IANA Considerations 2169 This document defines three new LLS TLV types to be allocated by 2170 IANA: MDR-Hello TLV, MDR-Metric TLV, and MDR-DD TLV. 2172 13. Acknowledgments 2174 Thanks to Aniket Desai for helpful discussions and comments, 2175 including the suggestion that Router Priority should come before MDR 2176 Level in the lexicographical comparison of (RtrPri, MDR Level, RID) 2177 when selecting MDRs and BMDRs, and that the MDR calculation should be 2178 repeated if it causes the MDR Level to change. Thanks also to Tom 2179 Henderson for helpful discussions and comments. 2181 14. Normative References 2183 [RFC2328] J. Moy. "OSPF Version 2", RFC 2328, April 1998. 2185 [RFC2740] R. Coltun, D. Ferguson, and J. Moy. "OSPF for IPv6", RFC 2186 2740, December 1999. 2188 [LLS] A. Zinin, A. Roy, L. Nguyen, B. Friedman, and D. Young, "OSPF 2189 Link-local Signaling", draft-ietf-ospf-lls-04.txt (work in 2190 progress), February 2008. 2192 [RFC2119] Bradner, S., "Key words for use in RFC's to Indicate 2193 Requirement Levels", RFC 2119, March 1997. 2195 15. Informative References 2197 [Lawler] E. Lawler. "Combinatorial Optimization: Networks and 2198 Matroids", Holt, Rinehart, and Winston, New York, 1976. 2200 [Suurballe] J.W. Suurballe and R.E. Tarjan. "A Quick Method for 2201 Finding Shortest Pairs of Disjoint Paths", Networks, Vol. 14, 2202 pp. 325-336, 1984. 2204 A. Packet Formats 2206 A.1. Options Field 2208 A new bit, called L (for LLS) is added to the OSPFv3 Options field 2209 (see Figure A.1). The mask for the bit is 0x200. Routers set the L 2210 bit in Hello and DD packets to indicate that the packet contains an 2211 LLS data block. Routers set the L bit in a self-originated router- 2212 LSA to indicate that the LSA is non-ackable. 2214 0 1 2 2215 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 2216 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+-+-+--+--+--+--+--+--+ 2217 | | | | | | | | | | | | | | |L|AF|*|*|DC| R| N|MC| E|V6| 2218 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+-+-+--+--+--+--+--+--+ 2220 Figure A.1: OSPFv3 Options field 2222 A.2. Link-Local Signaling 2224 OSPF-MDR uses link-local signaling (LLS) [LLS] to append the MDR- 2225 Hello TLV and MDR-Metric TLV to Hello packets, and to append the MDR- 2226 DD TLV to Database Description packets. Link-local signaling is an 2227 extension to OSPFv2 and OSPFv3 that allows the exchange of arbitrary 2228 data using existing OSPF packet types. Here we use LLS for OSPFv3, 2229 which is accomplished by adding an LLS data block at the end of the 2230 OSPFv3 packet. The OSPF packet length field does not include the 2231 length of the LLS data block, but the IPv6 packet length does include 2232 this length. 2234 A.2.1 LLS Data Block 2236 The data block used for link-local signaling is formatted as 2237 described below in Figure A.2. 2239 0 1 2 3 2240 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 2241 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2242 | Checksum | LLS Data Length | 2243 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2244 | | 2245 | LLS TLVs | 2246 . . 2247 . . 2248 . . 2249 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2250 Figure A.2: Format of LLS Data Block 2252 The Checksum field contains the standard IP checksum of the entire 2253 contents of the LLS block. 2255 The 16-bit LLS Data Length field contains the length (in 32-bit 2256 words) of the LLS block including the header and payload. 2257 Implementations should not use the Length field in the IPv6 packet 2258 header to determine the length of the LLS data block. 2260 The rest of the block contains a set of Type/Length/Value (TLV) 2261 triplets as described in the following section. All TLVs must be 2262 32-bit aligned (with padding if necessary). 2264 A.2.2 LLS TLV Format 2266 The contents of LLS data block is constructed using TLVs. See Figure 2267 A.3 for the TLV format. 2269 The type field contains the TLV ID which is unique for each type of 2270 TLV. The Length field contains the length of the Value field (in 2271 bytes) that is variable and contains arbitrary data. 2273 0 1 2 3 2274 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 2275 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2276 | Type | Length | 2277 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2278 | | 2279 . . 2280 . Value . 2281 . . 2282 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2283 Figure A.3: Format of LLS TLVs 2285 Note that TLVs are always padded to 32-bit boundary, but padding 2286 bytes are not included in TLV Length field (though it is included in 2287 the LLS Data Length field of the LLS block header). All unknown TLVs 2288 MUST be silently ignored. 2290 A.2.3 MDR-Hello TLV 2292 The MDR-Hello TLV is appended to each MANET Hello using LLS. It 2293 includes the current Hello sequence number (HSN) for the transmitting 2294 interface and the number of neighbors of each type that are listed in 2295 the body of the Hello (see Section 4.1). It also indicates whether 2296 the Hello is differential (via the D-bit), and whether the router is 2297 using full-topology adjacencies (via the A-bit). 2299 0 1 2 3 2300 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 2301 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2302 | Type | Length | 2303 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2304 | Hello Sequence Number | Reserved |A|D| 2305 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2306 | N1 | N2 | N3 | N4 | 2307 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2309 o Type: Set to 14. 2310 o Length: Set to 8. 2311 o Hello Sequence Number: A circular two octet unsigned integer 2312 indicating the current HSN for the transmitting interface. The 2313 HSN for the interface is incremented by 1 (modulo 2^16) every 2314 time a (differential or full) Hello is sent on the interface. 2315 o Reserved: Set to 0. Reserved for future use. 2316 o A (1 bit): Set to 1 if AdjConnectivity is 0, otherwise set to 0. 2317 o D (1 bit): Set to 1 for a differential Hello and 0 for a full 2318 Hello. 2319 o N1 (8 bits): The number of neighbors listed in the Hello that 2320 are in state Down. N1 is zero if the the Hello is not 2321 differential. 2322 o N2 (8 bits): The number of neighbors listed in the Hello that 2323 are in state Init. 2324 o N3 (8 bits): The number of neighbors listed in the Hello that 2325 are Dependent. 2326 o N4 (8 bits): The number of neighbors listed in the Hello that 2327 are Selected Advertised Neighbors. 2329 A.2.4 MDR-DD TLV 2331 When a Database Description packet is sent to a neighbor in state 2332 ExStart, an MDR-DD TLV is appended to the packet using LLS. It 2333 includes the same two Router IDs that are included in the DR and 2334 Backup DR fields of a Hello sent by the router, and is used to 2335 indicate the router's MDR Level and Parent(s). 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 | DR | 2343 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2344 | Backup DR | 2345 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2347 o Type: Set to 15. 2348 o Length: Set to 8. 2349 o DR: The same Router ID that is included in the DR field of a 2350 Hello sent by the router (see Section A.3). 2351 o Backup DR: The same Router ID that is included in the Backup DR 2352 field of a Hello sent by the router (see Section A.3). 2354 A.2.5 MDR-Metric TLV 2356 If LSAFullness is 1 or 2, an MDR-Metric TLV must be appended to each 2357 MANET Hello packet using LLS, unless all link metrics are 1. This 2358 TLV advertises the link metric for each bidirectional neighbor listed 2359 in the body of the Hello. At a minimum, this TLV advertises a single 2360 default metric. If the I bit is set, the Router ID and link metric 2361 are included for each bidirectional neighbor listed in the body of 2362 the Hello whose link metric is not equal to the default metric. This 2363 option reduces overhead when all neighbors have the same link metric, 2364 or only a few neighbors have a link metric that differs from the 2365 default metric. If the I bit is zero, the link metric is included 2366 for each bidirectional neighbor that is listed in the body of the 2367 Hello and the neighbor RIDs are omitted from the TLV. 2369 0 1 2 3 2370 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 2371 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2372 | Type | Length | 2373 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2374 | Default Metric | Reserved |I| 2375 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2376 | Neighbor ID (1) | 2377 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2378 | Neighbor ID (2) | 2379 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2380 | ... | 2381 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2382 | Metric (1) | Metric (2) | 2383 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2384 | ... 2385 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2387 o Type: Set to 16. 2388 o Length: Set to 4 + 6*N if the I bit is 1, and to 4 + 2*N if the I 2389 bit is 0, where N is the number of neighbors included in the TLV. 2390 o Default Metric: If the I bit is 1, this is the link metric that 2391 applies to every bidirectional neighbor listed in the body of 2392 the Hello whose RID is not listed in the Metric TLV. 2393 o Neighbor ID: If the I bit is 1, the RID is listed for each 2394 bidirectional neighbor (Lists 3 through 5 as defined in 2395 Section 4.1) in the body of the Hello whose link metric is not 2396 equal to the default metric. Omitted if the I bit is 0. 2397 o Metric: Link metric for each bidirectional neighbor, listed in 2398 the same order as the Neighbor IDs in the TLV if the I bit is 1, 2399 and in the same order as the Neighbor IDs of bidirectional 2400 neighbors (Lists 3 through 5 as defined in Section 4.1) 2401 in the body of the Hello if the I bit is 0. 2403 A.3. Hello Packet DR and Backup DR Fields 2405 The Designated Router (DR) and Backup DR fields of a Hello packet are 2406 set as follows: 2408 o DR: This field is the router's Parent, or is 0.0.0.0 if the 2409 Parent is null. The Parent of an MDR is always the router's 2410 own RID. 2412 o Backup DR: This field is the router's Backup Parent, or is 2413 0.0.0.0 if the Backup Parent is null. The Backup Parent of a 2414 BMDR is always the router's own RID. 2416 A.4. LSA Formats and Examples 2418 LSA formats are specified in [RFC2740] Section 3.4.3. Figure A.4 2419 below gives an example network map for a MANET in a single area. 2421 o Four MANET routers RT1, RT2, RT3, and RT4 are in area 1. 2422 o RT1's MANET interface has links to RT2 and RT3's MANET interfaces. 2423 o RT2's MANET interface has links to RT1 and RT3's MANET interfaces. 2424 o RT3's MANET interface has links to RT1, RT2, and RT3's MANET 2425 interfaces. 2426 o RT4's MANET interface has a link to RT3's MANET interface. 2427 o RT1 and RT2 have stub networks attached on broadcast interfaces. 2428 o RT3 has a transit network attached on a broadcast interface. 2430 .......................................... 2431 . Area 1. 2432 . + . 2433 . | . 2434 . | 2+---+1 1+---+ 2435 . N1 |---|RT1|----+ +---|RT4|---- 2436 . | +---+ |\ / +---+ 2437 . | | \ / . 2438 . + | \ N3 / . 2439 . | \ / . 2440 . + | \ / . 2441 . | | \ / . 2442 . | 2+---+1 | \ / . 2443 . N2 |---|RT2|----+-------+ . 2444 . | +---+ |1 . 2445 . | +---+ . 2446 . | |RT3|---------------- 2447 . + +---+ . 2448 . |2 . 2449 . +------------+ . 2450 . |1 N4 . 2451 . +---+ . 2452 . |RT5| . 2453 . +---+ . 2454 .......................................... 2456 Figure A.4: Area 1 with IP addresses shown 2458 Network IPv6 prefix 2459 ----------------------------------- 2460 N1 5f00:0000:c001:0200::/56 2461 N2 5f00:0000:c001:0300::/56 2462 N4 5f00:0000:c001:0400::/56 2464 Table 1: IPv6 link prefixes for sample network 2465 Router interface Interface ID IPv6 global unicast prefix 2466 ----------------------------------------------------------- 2467 RT1 LOOPBACK 0 5f00:0001::/64 2468 to N3 1 n/a 2469 to N1 2 5f00:0000:c001:0200::RT1/56 2470 RT2 LOOPBACK 0 5f00:0002::/64 2471 to N3 1 n/a 2472 to N2 2 5f00:0000:c001:0300::RT2/56 2473 RT3 LOOPBACK 0 5f00:0003::/64 2474 to N3 1 n/a 2475 to N4 2 5f00:0000:c001:0400::RT3/56 2476 RT4 LOOPBACK 0 5f00:0004::/64 2477 to N3 1 n/a 2478 RT5 to N4 1 5f00:0000:c001:0400::RT5/56 2480 Table 2: IPv6 link prefixes for sample network 2482 Router interface Interface ID link-local address 2483 ------------------------------------------------------- 2484 RT1 LOOPBACK 0 n/a 2485 to N1 1 fe80:0001::RT1 2486 to N3 2 fe80:0002::RT1 2487 RT2 LOOPBACK 0 n/a 2488 to N2 1 fe80:0001::RT2 2489 to N3 2 fe80:0002::RT2 2490 RT3 LOOPBACK 0 n/a 2491 to N3 1 fe80:0001::RT3 2492 to N4 2 fe80:0002::RT3 2493 RT4 LOOPBACK 0 n/a 2494 to N3 1 fe80:0001::RT4 2495 RT5 to N4 1 fe80:0002::RT5 2497 Table 3: OSPF Interface IDs and link-local addresses 2499 A.4.1 Router-LSAs 2501 As an example, consider the router-LSA that node RT3 would originate. 2502 The node consists of one MANET, one broadcast, and one loopback 2503 interface. 2505 RT3's router-LSA 2507 LS age = DoNotAge+0 ;newly originated 2508 LS type = 0x2001 ;router-LSA 2509 Link State ID = 0 ;first fragment 2510 Advertising Router = 192.1.1.3 ;RT3's Router ID 2511 bit E = 0 ;not an AS boundary router 2512 bit B = 1 ;area border router 2513 Options = (V6-bit|E-bit|R-bit) 2514 Type = 1 ;p2p link to RT1 2515 Metric = 1 ;cost to RT1 2516 Interface ID = 1 ;Interface ID 2517 Neighbor Interface ID = 1 ;Interface ID 2518 Neighbor Router ID = 192.1.1.1 ;RT1's Router ID 2519 Type = 1 ;p2p link to RT2 2520 Metric = 1 ;cost to RT2 2521 Interface ID = 1 ;Interface ID 2522 Neighbor Interface ID = 1 ;Interface ID 2523 Neighbor Router ID = 192.1.1.2 ;RT2's Router ID 2524 Type = 1 ;p2p link to RT4 2525 Metric = 1 ;cost to RT4 2526 Interface ID = 1 ;Interface ID 2527 Neighbor Interface ID = 1 ;Interface ID 2528 Neighbor Router ID = 192.1.1.4 ;RT4's Router ID 2529 Type = 2 ;connects to N4 2530 Metric = 1 ;cost to N4 2531 Interface ID = 2 ;RT3's Interface ID 2532 Neighbor Interface ID = 1 ;RT5's Interface ID (elected DR) 2533 Neighbor Router ID = 192.1.1.5 ;RT5's Router ID (elected DR) 2535 A.4.2 Link-LSAs 2537 Consider the link-LSA that RT3 would originate for its MANET 2538 interface. 2540 RT3's Link-LSA for its MANET interface 2542 LS age = DoNotAge+0 ;newly originated 2543 LS type = 0x0008 ;Link-LSA 2544 Link State ID = 1 ;Interface ID 2545 Advertising Router = 192.1.1.3 ;RT3's Router ID 2546 RtrPri = 1 ;default priority 2547 Options = (V6-bit|E-bit|R-bit) 2548 Link-local Interface Address = fe80:0001::RT3 2549 # prefixes = 0 ;no global unicast address 2551 A.4.3 Intra-Area-Prefix-LSAs 2553 A MANET node originates an intra-area-prefix-LSA to advertise its own 2554 prefixes, and those of its attached networks or stub links. As an 2555 example, consider the intra-area-prefix-LSA that RT3 will build. 2557 RT2's intra-area-prefix-LSA for its own prefixes 2559 LS age = DoNotAge+0 ;newly originated 2560 LS type = 0x2009 ;intra-area-prefix-LSA 2561 Link State ID = 177 ;or something 2562 Advertising Router = 192.1.1.3 ;RT3's Router ID 2563 # prefixes = 2 2564 Referenced LS type = 0x2001 ;router-LSA reference 2565 Referenced Link State ID = 0 ;always 0 for router-LSA reference 2566 Referenced Advertising Router = 192.1.1.3 ;RT2's Router ID 2567 PrefixLength = 64 ;prefix on RT3's LOOPBACK 2568 PrefixOptions = 0 2569 Metric = 0 ;cost of RT3's LOOPBACK 2570 Address Prefix = 5f00:0003::/64 2571 PrefixLength = 56 ;prefix on RT3's interface 2 2572 PrefixOptions = 0 2573 Metric = 1 ;cost of RT3's interface 2 2574 Address Prefix = 5f00:0000:c001:0400::RT3/56 ;pad 2576 B. Detailed Algorithms for MDR/BMDR Selection 2578 This section provides detailed algorithms for Step 2.4 of Phase 2 2579 (MDR Selection) and Step 3.2 of Phase 3 (BMDR Selection) of the MDR 2580 selection algorithm described in Section 5. Step 2.4 uses a breadth- 2581 first search (BFS) algorithm, and Step 3.2 uses an efficient 2582 algorithm for finding pairs of node-disjoint paths from Rmax to all 2583 other neighbors. Both algorithms run in O(d^2) time, where d is the 2584 number of neighbors. 2586 For convenience, in the following description, the term "bi-neighbor" 2587 will be used as an abbreviation for "bidirectional neighbor". Also, 2588 node i denotes the router performing the calculation. 2590 B.1. Detailed Algorithm for Step 2.4 (MDR Selection) 2592 The following algorithm performs Step 2.4 of the MDR selection 2593 algorithm, and assumes that Phase 1 and Steps 2.1 through 2.3 have 2594 been performed, so that the neighbor connectivity matrix NCM has been 2595 computed, and Rmax is the bi-neighbor with the (lexicographically) 2596 largest value of (RtrPri, MDR Level, RID). The BFS algorithm uses a 2597 FIFO queue so that all nodes 1 hop from node Rmax are processed 2598 first, then 2 hops, etc. When the BFS algorithm terminates, hops(u), 2599 for each bi-neighbor node u of node i, will be equal to the minimum 2600 number of hops from node Rmax to node u, using only intermediate 2601 nodes that are bi-neighbors of node i and that have a larger value of 2602 (RtrPri, MDR Level, RID) than node i. The algorithm also computes, 2603 for each node u, the tree parent p(u) and the second node r(u) on the 2604 tree path from Rmax to u, which will be used in Step 3.2 2606 (a) Compute a matrix of link costs c(u,v) for each pair of 2607 bi-neighbors u and v as follows: If node u has a larger value 2608 of (RtrPri, MDR Level, RID) than node i, and NCM(u,v) = 1, 2609 then set c(u,v) to 1. Otherwise, set c(u,v) to infinity. 2610 (Note that the matrix NCM(u,v) is symmetric, but the matrix 2611 c(u,v) is not.) 2613 (b) Set hops(u) = infinity for all bi-neighbors u other than Rmax, 2614 and set hops(Rmax) = 0. Initially, p(u) is undefined for each 2615 neighbor u. For each bi-neighbor u such that c(Rmax,u) = 1, 2616 set r(u) = u; for all other u, r(u) is initially undefined. 2617 Add node Rmax to the FIFO queue. 2619 (c) While the FIFO queue is nonempty: 2620 Remove the node at the head of the queue; call it node u. 2621 For each bi-neighbor v of node i such that c(u,v) = 1: 2622 If hops(v) > hops(u) + 1, then set hops(v) = hops(u) + 1, 2623 set p(v) = u, set r(v) = r(u) if hops(v) > 1, and add 2624 node v to the tail of the queue. 2626 B.2. Detailed Algorithm for Step 3.2 (BMDR Selection) 2628 Step 3.2 of the MDR selection algorithm requires the router to 2629 determine whether there exist two node-disjoint paths from Rmax to 2630 each other bi-neighbor u, via bi-neighbors that have a larger value 2631 of (RtrPri, MDR Level, RID) than the router itself. This information 2632 is needed to determine whether the router should select itself as a 2633 BMDR. 2635 It is possible to determine separately for each bi-neighbor u whether 2636 there exist two node-disjoint paths from Rmax to u, using the well- 2637 known augmenting path algorithm [Lawler] which runs in O(n^2) time, 2638 but this must be done for all bi-neighbors u, thus requiring a total 2639 run time of O(n^3). The algorithm described below makes the same 2640 determination simultaneously for all bi-neighbors u, achieving a much 2641 faster total run time of O(n^2). The algorithm is a simplified 2642 variation of the Suurballe-Tarjan algorithm [Suurballe] for finding 2643 pairs of disjoint paths. 2645 The algorithm described below uses the following output of Phase 2: 2646 the tree parent p(u) of each node (which defines the BFS tree 2647 computed in Phase 2), and the second node r(u) on the tree path from 2648 Rmax to u. 2650 The algorithm uses the following concepts. For any node u on the BFS 2651 tree other than Rmax, we define g(u) to be the first labeled node on 2652 the reverse tree path from u to Rmax, if such a labeled node exists 2653 other than Rmax. (The reverse tree path consists of u, p(u), 2654 p(p(u)), ..., Rmax.) If no such labeled node exists, then g(u) is 2655 defined to be r(u). In particular, if u is labeled then g(u) = u. 2656 Note that g(u) either must be labeled or must be a neighbor of Rmax. 2658 For any node k that either is labeled or is a neighbor of Rmax, we 2659 define the unlabeled subtree rooted at k, denoted S(k), to be the set 2660 of nodes u such that g(u) = k. Thus, S(k) includes node k itself and 2661 the set of unlabeled nodes downstream of k on the BFS tree that can 2662 be reached without going through any labeled nodes. This set can be 2663 obtained in linear time using a depth-first search starting at node 2664 k, and using labeled nodes to indicate the boundaries of the search. 2665 Note that g(u) and S(k) are not maintained as variables in the 2666 algorithm given below, but simply refer to the definitions given 2667 above. 2669 The BMDR algorithm maintains a set B, which is initially empty. A 2670 node u is added to B when it is known that two node-disjoint paths 2671 exist from Rmax to u via nodes that have a larger value of (RtrPri, 2672 MDR Level, RID) than the router itself. When the algorithm 2673 terminates, B consists of all nodes that have this property. 2675 The algorithm consists of the following two steps. 2677 (a) Mark Rmax as labeled. For each pair of nodes u, v on the BFS 2678 tree other than Rmax such that r(u) is not equal to r(v) (i.e., 2679 u and v have different second nodes), NCM(u,v) = 1, and node u 2680 has a greater value of (RtrPri, MDR level, RID) than the router 2681 itself, add v to B. (Clearly there are two disjoint paths from 2682 Rmax to v.) 2684 (b) While there exists a node in B that is not labeled, do the 2685 following. Choose any node k in B that is not labeled, and let 2686 j = g(k). Now mark k as labeled. (This creates a new unlabeled 2687 subtree S(k), and makes S(j) smaller by removing S(k) from it.) 2688 For each pair of nodes u, v such that u is in S(k), v is in 2689 S(j), and NCM(u,v) = 1: 2691 o If u has a larger value of (RtrPri, MDR level, RID) than the 2692 router itself, and v is not in B, then add v to B. 2694 o If v has a larger value of (RtrPri, MDR level, RID) than the 2695 router itself, and u is not in B, then add u to B. 2697 A simplified version of the algorithm MAY be performed by omitting 2698 step (b). However, the simplified algorithm will result in more 2699 BMDRs, and is not recommended if AdjConnectivity = 2 since it will 2700 result in more adjacencies. 2702 The above algorithm can be executed in O(n^2) time, where n is the 2703 number of neighbors. Step (a) clearly requires O(n^2) time since it 2704 considers all pairs of nodes u and v. Step (b) also requires O(n^2) 2705 time because each pair of nodes is considered at most once. This is 2706 because labeling nodes divides unlabeled subtrees into smaller 2707 unlabeled subtrees, and a given pair u, v is considered only the 2708 first time u and v belong to different unlabeled subtrees. 2710 C. Min-Cost LSA Algorithm 2712 This section describes the algorithm for determining which MANET 2713 neighbors to include in the router-LSA when LSAFullness is 1. The 2714 min-cost LSA algorithm ensures that the link-state database provides 2715 sufficient information to calculate at least one shortest (minimum- 2716 cost) path to each destination. The algorithm assumes that a router 2717 may have multiple interfaces, at least one of which is a MANET 2718 interface. The algorithm becomes significantly simpler if the router 2719 has only a single (MANET) interface. 2721 The input to this algorithm includes information obtained from Hellos 2722 received from each neighbor on each MANET interface, including the 2723 neighbor's Bidirectional Neighbor Set (BNS), Dependent Neighbor Set 2724 (DNS), Selected Advertised Neighbor Set (SANS), and link metrics. 2725 The input also includes the link-state database if the router has a 2726 non-MANET interface. 2728 The output of the algorithm is the router's SANS for each MANET 2729 interface. The SANS is used to construct the router-LSA as described 2730 in Section 9.4. The min-cost LSA algorithm must be run to update the 2731 SANS (and possibly originate a new router-LSA) either periodically 2732 just before sending each Hello, or whenever any of the following 2733 events occurs: 2735 o The state or routability of a neighbor changes. 2736 o A Hello received from a neighbor indicates a change in its 2737 MDR Level, Router Priority, FullHelloRcvd, BNS, DNS, SANS, 2738 Parent(s), or link metrics. 2739 o An LSA originated by a non-MANET neighbor is received. 2741 Although the algorithm described below runs in O(d^3) time, where d 2742 is the number of neighbors, an incremental version for a single 2743 topology change runs in O(d^2) time, as discussed following the 2744 algorithm description. 2746 For convenience, in the following description, the term "bi-neighbor" 2747 will be used as an abbreviation for "bidirectional neighbor". Also, 2748 router i will denote the router doing the calculation. To perform 2749 the min-cost LSA algorithm, the following steps are performed. 2751 (1) Create the neighbor connectivity matrix (NCM) for each MANET 2752 interface, as described in Section 5.1. Create the multiple- 2753 interface neighbor connectivity matrix MNCM as follows. For each 2754 bi-neighbor j, set MNCM(i,j) = MNCM(j,i) = 1. For each pair j, k 2755 of MANET bi-neighbors, set MNCM(j,k) = 1 if NCM(j,k) equals 1 for 2756 any MANET interface. For each pair j, k of non-MANET bi- 2757 neighbors, set MNCM(j,k) = 1 if the link-state database indicates 2758 that a direct link exists between j and k. Otherwise, set 2759 MNCM(j,k) = 0. (Note that a given router can be a neighbor on 2760 both a MANET interface and a non-MANET interface.) 2762 (2) Create the inter-neighbor cost matrix (COST) as follows. For 2763 each pair j, k of routers such that each of j and k is a bi- 2764 neighbor or router i itself: 2766 (a) If MNCM(j,k) = 1, set COST(j,k) to the metric of the link 2767 from j to k obtained from j's Hellos (for a MANET interface), 2768 or from the link-state database (for a non-MANET interface). 2769 If there are multiple links from j to k (via multiple 2770 interfaces), COST(j,k) is set to the minimum cost of these 2771 links. 2773 (b) Otherwise, set COST(j,k) to LSInfinity. 2775 (3) Create the backbone neighbor matrix (BNM) as follows. BNM 2776 indicates which pairs of MANET bi-neighbors are backbone 2777 neighbors of each other, as defined in Section 9.2.1. If 2778 adjacency reduction is not used (AdjConnectivity = 0), set all 2779 entries of BNM to zero and proceed to step 4. 2781 In the following, if a link exists from router j to router k on 2782 more than one interface, we consider only interfaces for which 2783 the cost from j to k equals COST(j,k); such interfaces will be 2784 called "candidate" interfaces. 2786 For each pair j, k of MANET bi-neighbors, BNM(j,k) is set to 1 if 2787 j and k are backbone neighbors of each other on a candidate MANET 2788 interface. That is, BNM(j,k) is set to 1 if, for any candidate 2789 MANET interface, NCM(j,k) = 1 and either of the following 2790 conditions is satisfied: 2792 (a) Router k is included in j's DNS or router j is included in 2793 k's DNS. 2795 (b) Router j is the (Backup) Parent of router k or router k is 2796 the (Backup) Parent of router j. 2798 Otherwise, BNM(j,k) is set to 0. 2800 (4) Create the selected advertised neighbor matrix (SANM) as follows. 2801 For each pair j, k of routers such that each of j and k is a bi- 2802 neighbor or router i itself, SANM(j,k) is set to 1 if, for any 2803 candidate MANET interface, NCM(j,k) = 1 and k is included in j's 2804 SANS. Otherwise, SANM(j,k) is set to 0. Note that SANM(i,k) is 2805 set to 1 if k is currently a selected advertised neighbor. 2807 (5) Compute the new set of selected advertised neighbors as follows. 2808 For each MANET bi-neighbor j, initialize the bit variable 2809 new_sel_adv(j) to 0. (This bit will be set to 1 if j is 2810 selected.) For each MANET bi-neighbor j: 2812 (a) If j is a bi-neighbor on more than one interface, consider 2813 only candidate interfaces (for which the cost to j is 2814 minimum). If one of the candidate interfaces is a non-MANET 2815 interface, examine the next neighbor (j is not selected since 2816 it will be advertised anyway). 2818 (b) If adjacency reduction is used, and one of the candidate 2819 interfaces is a MANET interface on which j is a backbone 2820 neighbor (see Section 9.2), examine the next neighbor (j is 2821 not selected since it will be advertised anyway). 2823 (c) Otherwise, if there is more than one candidate MANET 2824 interface, select the "preferred" interface by using the 2825 following preference rules in the given order: an interface 2826 is preferred if (1) router i's SANS for that interface 2827 already includes j, (2) router i's Router Priority is larger 2828 on that interface, and (3) router i's MDR level is larger on 2829 that interface. 2831 (d) For each bi-neighbor k (on any interface) such that COST(k,j) 2832 > COST(k,i) + COST(i,j), determine whether there exists 2833 another bi-neighbor u such that either COST(k,u) + COST(u,j) 2834 < COST(k,i) + COST(i,j), or COST(k,u) + COST(u,j) = COST(k,i) 2835 + COST(i,j) and either of the following conditions is true: 2837 o BNM(u,j) = 1, or 2838 o (SANM(j,u), SANM(u,j), RtrPri(u), RID(u)) 2839 is lexicographically greater than 2840 (SANM(j,i), SANM(i,j), RtrPri(i), RID(i)). 2842 If for some such bi-neighbor k, there does not exist such a 2843 bi-neighbor u, then set new_sel_adv(j) = 1. 2845 (6) For each MANET interface I, update the SANS to equal the set of 2846 all bi-neighbors j such that new_sel_adv(j) = 1 and I is the 2847 preferred interface for j. 2849 (7) With the SANS updated, a new router-LSA may need to be originated 2850 as described in Section 9.4. 2852 The lexicographical comparison of Step 5d gives preference to links 2853 that are already advertised, in order to improve LSA stability. 2855 The above algorithm can be run in O(d^2) time if a single link change 2856 occurs. For example, if link (x,y) fails where x and y are neighbors 2857 of router i, and either SANS(x,y) = 1 or BNM(x,y) = 1, then Step 5 2858 need only be performed for pairs j, k such that either j or k is 2859 equal to x or y. 2861 D. Non-Ackable LSAs for Periodic Flooding 2863 In a highly mobile network, it is possible that a router almost 2864 always originates a new router-LSA every MinLSInterval seconds. In 2865 this case, it should not be necessary to send Acks for such an LSA, 2866 or to retransmit such an LSA as a unicast, or to describe such an LSA 2867 in a DD packet. In this case, the originator of an LSA MAY indicate 2868 that the router-LSA is "non-ackable" by setting a bit (to be 2869 specified) in the options field of the LSA. For example, a router 2870 can originate non-ackable LSAs if it determines (e.g., based on an 2871 exponential moving average) that a new LSA is originated every 2872 MinLSInterval seconds at least 90 percent of the time. (Simulations 2873 can be used to determine the best threshold.) 2875 A non-ackable LSA is never acknowledged, nor is it ever retransmitted 2876 as a unicast or described in a DD packet, thus saving substantial 2877 overhead. However, the originating router must periodically 2878 retransmit the current instance of its router-LSA as a multicast 2879 (until it originates a new LSA, which will usually happen before the 2880 previous instance is retransmitted), and each MDR must periodically 2881 retransmit each non-ackable LSA as a multicast (until it receives a 2882 new instance of the LSA, which will usually happen before the 2883 previous instance is retransmitted). For this option to work, 2884 RxmtInterval must be larger than MinLSInterval so that a new instance 2885 of the LSA is usually received before the previous one is 2886 retransmitted. Note that the reception of a retransmitted 2887 (duplicate) LSA does not result in immediate forwarding of the LSA; 2888 only a new LSA (with a larger sequence number) may be forwarded 2889 immediately, according to the flooding procedure of Section 8. 2891 E. Simulation Results 2893 This section presents simulation results that predict the performance 2894 of OSPF-MDR for up to 140 nodes with min-cost LSAs and up to 200 2895 nodes with minimal LSAs. The results were obtained using the GTNetS 2896 simulator with OSPF-MDR version 1.00, available at 2897 http://hipserver.mct.phantomworks.org/ietf/ospf. 2899 The following scenario parameter values were used: radio range = 200 2900 m and 250 m, grid length = 500 m, wireless alpha = 0.5, (maximum) 2901 velocity = 10 m/s, pause time = 0, packet rate = 10 pkts/s, packet 2902 size = 40 bytes, random seed = 8, start time (for gathering 2903 statistics) = 1800 s. The stop time was 3600 s for up to 80 nodes 2904 and 2700 s for more than 80 nodes. The source and destination are 2905 selected randomly for each generated UDP packet. The simulated MAC 2906 protocol is 802.11b. 2908 Tables 4 and 6 show the results for the default configuration of 2909 OSPF-MDR, except that differential Hellos were used (2HopRefresh = 3) 2910 since they are recommended when the number of neighbors is large. 2911 Tables 5 and 7 show the results for the same configuration except 2912 that minimal LSAs were used instead of min-cost LSAs. The tables 2913 show the results for total OSPF overhead in kb/s, the total number of 2914 OSPF packets per second, the delivery ratio for UDP packets, and the 2915 average number of hops traveled by UDP packets that reach their 2916 destination. 2918 Tables 5 and 7 for minimal LSAs also show the following statistics: 2919 the average number of bidirectional neighbors per node, the average 2920 number of fully adjacent neighbors per node, the number of changes in 2921 the set of bidirectional neighbors per node per second, and the 2922 number of changes in the set of fully adjacent neighbors per node per 2923 second. These statistics do not change significantly when min-cost 2924 LSAs are used instead of minimal LSAs. 2926 The results show that OSPF-MDR achieves good performance for up to at 2927 least 140 nodes when min-cost LSAs are used, and up to at least 200 2928 nodes when minimal LSAs are used. Also, the results for the number 2929 of hops show that the routes obtained with minimal LSAs are only 2.3% 2930 to 3.5% longer than with min-cost LSAs when the range is 250 m, and 2931 3.9% to 7% longer when the range is 200 m. 2933 The results also show that the number of adjacencies per node and the 2934 number of adjacency changes per node per second do not increase as 2935 the number of nodes increases, and are dramatically smaller than the 2936 number of neighbors per node and the number of neighbor changes per 2937 node per second, respectively. These factors contribute to the low 2938 overhead achieved by OSPF-MDR. Additional simulation results for 2939 OSPF-MDR can be found at http://www.manet-routing.org. 2941 Number of nodes 2942 20 40 60 80 100 120 140 2943 ------------------------------------------------------------------ 2944 OSPF kb/s 27.4 75.0 175.9 250.4 344.8 458.1 571.4 2945 OSPF pkts/s 29.9 69.8 124.2 164.8 210.5 255.7 297.0 2946 Delivery ratio .970 .969 .953 .959 .959 .958 .956 2947 Avg no. hops 1.432 1.351 1.388 1.371 1.411 1.361 1.373 2949 Table 4: Results for range 250 m with min-cost LSAs 2950 Number of nodes 2951 20 40 60 80 120 160 200 2952 ------------------------------------------------------------------ 2953 OSPF kb/s 16.0 43.1 91.6 133.5 243.2 405.5 622.4 2954 OSPF pkts/sec 19.3 43.9 78.3 103.7 164.3 241.2 318.1 2955 Delivery ratio .970 .967 .952 .954 .958 .948 .956 2956 Avg no. hops 1.467 1.382 1.431 1.410 1.409 1.425 1.413 2957 Avg no. nbrs/node 11.35 25.83 36.33 50.18 76.03 98.86 125.90 2958 Avg no. adjs/node 2.75 2.55 2.57 2.33 2.35 2.36 2.16 2959 Nbr changes/node/s .17 .37 .57 .75 1.20 1.63 2.08 2960 Adj changes/node/s .04 .04 .05 .04 .03 .04 .04 2962 Table 5: Results for range 250 m with minimal LSAs 2964 Number of nodes 2965 20 40 60 80 100 120 140 2966 ------------------------------------------------------------------ 2967 OSPF kb/s 41.3 121.6 285.6 403.2 591.8 765.7 940.1 2968 OSPF pkts/s 37.9 82.8 136.4 169.6 210.3 250.1 285.7 2969 Delivery ratio .924 .923 .899 .900 .895 .896 .894 2970 Avg no. hops 1.783 1.625 1.666 1.633 1.680 1.609 1.628 2972 Table 6: Results for range 200 m with min-cost LSAs 2974 Number of nodes 2975 20 40 60 80 120 160 200 2976 ------------------------------------------------------------------ 2977 OSPF kb/s 26.6 64.6 151.2 205.3 355.6 568.8 811.9 2978 OSPF pkts/sec 28.6 59.6 113.5 144.1 221.0 313.3 402.6 2979 Delivery ratio .931 .926 .899 .902 .899 .908 .905 2980 Avg no. hops 1.853 1.709 1.771 1.733 1.722 1.771 1.739 2981 Avg no. nbrs/node 7.65 18.16 25.30 35.43 53.14 68.44 87.25 2982 Avg no. adjs/node 3.09 2.72 2.88 2.67 2.39 2.42 2.29 2983 Nbr changes/node/s .20 .47 .69 .94 1.51 1.97 2.56 2984 Adj changes/node/s .08 .07 .09 .07 .06 .06 .06 2986 Table 7: Results for range 200 m with minimal LSAs 2988 Authors' Addresses 2990 Richard G. Ogier 2991 SRI International 2992 Email: rich.ogier@earthlink.net 2994 Phil Spagnolo 2995 Boeing Phantom Works 2996 Email: phillip.a.spagnolo@boeing.com 2998 Intellectual Property Statement 3000 The IETF takes no position regarding the validity or scope of any 3001 Intellectual Property Rights or other rights that might be claimed to 3002 pertain to the implementation or use of the technology described in 3003 this document or the extent to which any license under such rights 3004 might or might not be available; nor does it represent that it has 3005 made any independent effort to identify any such rights. Information 3006 on the procedures with respect to rights in RFC documents can be 3007 found in BCP 78 and BCP 79. 3009 Copies of IPR disclosures made to the IETF Secretariat and any 3010 assurances of licenses to be made available, or the result of an 3011 attempt made to obtain a general license or permission for the use of 3012 such proprietary rights by implementers or users of this 3013 specification can be obtained from the IETF on-line IPR repository at 3014 http://www.ietf.org/ipr. 3016 The IETF invites any interested party to bring to its attention any 3017 copyrights, patents or patent applications, or other proprietary 3018 rights that may cover technology that may be required to implement 3019 this standard. Please address the information to the IETF at ietf- 3020 ipr@ietf.org. 3022 Disclaimer of Validity 3024 This document and the information contained herein are provided on an 3025 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 3026 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 3027 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 3028 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 3029 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 3030 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 3032 Copyright Statement 3034 Copyright (C) The IETF Trust (2008). This document is subject to the 3035 rights, licenses and restrictions contained in BCP 78, and except as 3036 set forth therein, the authors retain all their rights. 3038 Acknowledgment 3040 Funding for the RFC Editor function is currently provided by the 3041 Internet Society.