idnits 2.17.1 draft-ietf-ospf-manet-mdr-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.i or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? -- It seems you're using the 'non-IETF stream' Licence Notice instead Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 2620 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 (January 28, 2009) is 5565 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 ---------------------------------------------------------------------------- == Outdated reference: A later version (-08) exists of draft-ietf-ospf-lls-06 Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group R. Ogier 3 Internet-Draft SRI International 4 Intended status: Experimental P. Spagnolo 5 Expires: August 1, 2009 Boeing 6 January 28, 2009 8 MANET Extension of OSPF using CDS Flooding 9 draft-ietf-ospf-manet-mdr-05.txt 11 Status of this Memo 13 This Internet-Draft is submitted to IETF in full conformance with the 14 provisions of BCP 78 and BCP 79. 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note that 18 other groups may also distribute working documents as Internet- 19 Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six months 22 and may be updated, replaced, or obsoleted by other documents at any 23 time. It is inappropriate to use Internet-Drafts as reference 24 material or to cite them other than as "work in progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/1id-abstracts.html 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html 32 Copyright Notice 34 Copyright (c) 2009 IETF Trust and the persons identified as the 35 document authors. All rights reserved. 37 This document is subject to BCP 78 and the IETF Trust's Legal 38 Provisions Relating to IETF Documents 39 (http://trustee.ietf.org/license-info) in effect on the date of 40 publication of this document. Please review these documents 41 carefully, as they describe your rights and restrictions with respect 42 to this document. 44 Abstract 46 This document specifies an extension of OSPFv3 to support mobile ad 47 hoc networks (MANETs). The extension, called OSPF-MDR, is designed 48 as a new OSPF interface type for MANETs. OSPF-MDR is based on the 49 selection of a subset of MANET routers, consisting of MANET 50 Designated Routers (MDRs) and Backup MDRs. The MDRs form a connected 51 dominating set (CDS), and the MDRs and Backup MDRs together form a 52 biconnected CDS for robustness. This CDS is exploited in two ways. 53 First, to reduce flooding overhead, an optimized flooding procedure 54 is used in which only (Backup) MDRs flood new link state 55 advertisements (LSAs) back out the receiving interface; reliable 56 flooding is ensured by retransmitting LSAs along adjacencies. 57 Second, adjacencies are formed only between (Backup) MDRs and a 58 subset of their neighbors, allowing for much better scaling in dense 59 networks. The CDS is constructed using 2-hop neighbor information 60 provided in a Hello protocol extension. The Hello protocol is 61 further optimized by allowing differential Hellos that report only 62 changes in neighbor states. Options are specified for originating 63 router-LSAs that provide full or partial topology information, 64 allowing overhead to be reduced by advertising less topology 65 information. 67 Table of Contents 69 1 Introduction ................................................. 4 70 1.1 Terminology .................................................. 5 71 2 Overview ..................................................... 7 72 2.1 Selection of MDRs, BMDRs, Parents, and Adjacencies ........... 7 73 2.2 Flooding Procedure ........................................... 8 74 2.3 Link State Acknowledgments ................................... 9 75 2.4 Routable Neighbors ........................................... 9 76 2.5 Partial and Full Topology LSAs .............................. 10 77 2.6 Hello Protocol .............................................. 11 78 3 Interface and Neighbor Data Structures ...................... 11 79 3.1 Changes to Interface Data Structure ......................... 11 80 3.2 New Configurable Interface Parameters ....................... 12 81 3.3 Changes to Neighbor Data Structure .......................... 14 82 4 Hello Protocol .............................................. 16 83 4.1 Sending Hello Packets ....................................... 16 84 4.2 Receiving Hello Packets ..................................... 19 85 4.3 Neighbor Acceptance Condition ............................... 22 86 5 MDR Selection Algorithm ..................................... 22 87 5.1 Phase 1: Creating the Neighbor Connectivity Matrix .......... 24 88 5.2 Phase 2: MDR Selection ...................................... 25 89 5.3 Phase 3: Backup MDR Selection ............................... 26 90 5.4 Phase 4: Parent Selection ................................... 27 91 5.5 Phase 5: Optional Selection of Non-Flooding MDRs ............ 28 92 6 Interface State Machine ..................................... 28 93 6.1 Interface States ............................................ 28 94 6.2 Events that Cause Interface State Changes ................... 29 95 6.3 Changes to Interface State Machine .......................... 29 96 7 Adjacency Maintenance ....................................... 30 97 7.1 Changes to Neighbor State Machine ........................... 30 98 7.2 Whether to Become Adjacent .................................. 31 99 7.3 Whether to Eliminate an Adjacency ........................... 32 100 7.4 Sending Database Description Packets ........................ 32 101 7.5 Receiving Database Description Packets ...................... 32 102 8 Flooding Procedure .......................................... 34 103 8.1 LSA Forwarding Procedure .................................... 34 104 8.2 Sending Link State Acknowledgments .......................... 37 105 8.3 Retransmitting LSAs ......................................... 38 106 8.4 Receiving Link State Acknowledgments ........................ 38 107 9 Router-LSAs ................................................. 39 108 9.1 Routable Neighbors .......................................... 40 109 9.2 Backbone Neighbors .......................................... 41 110 9.3 Selected Advertised Neighbors ............................... 41 111 9.4 Originating Router-LSAs ..................................... 42 112 10 Calculating the Routing Table ............................... 43 113 11 Security Considerations ..................................... 44 114 12 IANA Considerations ......................................... 46 115 13 Acknowledgments ............................................. 46 116 14 Normative References ........................................ 46 117 15 Informative References ...................................... 47 118 A Packet Formats .............................................. 47 119 A.1 Options Field ............................................... 47 120 A.2 Link-Local Signaling ........................................ 47 121 A.3 Hello Packet DR and Backup DR Fields ........................ 51 122 A.4 LSA Formats and Examples .................................... 52 123 B Detailed Algorithms for MDR/BMDR Selection .................. 55 124 B.1 Detailed Algorithm for Step 2.4 (MDR Selection) ............. 55 125 B.2 Detailed Algorithm for Step 3.2 (BMDR Selection) ............ 56 126 C Min-Cost LSA Algorithm ...................................... 58 127 D Non-Ackable LSAs for Periodic Flooding ...................... 61 128 E Simulation Results .......................................... 61 129 Authors Addresses ........................................... 63 131 1. Introduction 133 This document specifies an extension of OSPFv3 [RFC5340] to support a 134 new interface type for mobile ad hoc networks (MANETs), i.e., for 135 broadcast-capable, multihop wireless networks in which routers and 136 hosts can be mobile. Note that OSPFv3 is specified by describing the 137 modifications to OSPFv2 [RFC2328]. This MANET extension of OSPFv3 is 138 also applicable to non-mobile mesh networks using layer-3 routing. 139 This extension does not preclude the use of any existing OSPF 140 interface types, and is fully compatible with legacy OSPFv3 141 implementations. 143 Existing OSPF interface types do not perform adequately in MANETs, 144 due to scaling issues regarding the flooding protocol operation, 145 inability of the Designated Router election protocol to converge in 146 all scenarios, and large numbers of adjacencies when using a Point- 147 to-Multipoint interface type. 149 The approach taken is to generalize the concept of an OSPF Designated 150 Router (DR) and Backup DR to multihop wireless networks, in order to 151 reduce overhead by reducing the number of routers that must flood new 152 LSAs and reducing the number of adjacencies. The generalized 153 (Backup) Designated Routers are called (Backup) MANET Designated 154 Routers (MDRs). The MDRs form a connected dominating set (CDS), and 155 the MDRs and Backup MDRs together form a biconnected CDS for 156 robustness (if the network itself is biconnected). By definition, 157 each router in the MANET either belongs to the CDS or is one hop away 158 from it. A distributed algorithm is used to select and dynamically 159 maintain the biconnected CDS. Adjacencies are established only 160 between (Backup) MDRs and a subset of their neighbors, thus resulting 161 in a dramatic reduction in the number of adjacencies in dense 162 networks, compared to the approach of forming adjacencies between all 163 neighbor pairs. The OSPF extension is called OSPF-MDR. 165 Hello packets are modified, using OSPF link-local signaling [LLS], 166 for two purposes: to provide neighbors with 2-hop neighbor 167 information that is required by the MDR selection algorithm, and to 168 allow differential Hellos that report only changes in neighbor 169 states. Differential Hellos can be sent more frequently without a 170 significant increase in overhead, in order to respond more quickly to 171 topology changes. 173 Each MANET router advertises a subset of its MANET neighbors as 174 point-to-point links in its router-LSA. The choice of which 175 neighbors to advertise is flexible, allowing overhead to be reduced 176 by advertising less topology information. Options are specified for 177 originating router-LSAs that provide full or partial topology 178 information. 180 This document is organized as follows. Section 2 presents an 181 overview of OSPF-MDR, Section 3 presents the new interface and 182 neighbor data items that are required for the extension, Section 4 183 describes the Hello protocol, including procedures for maintaining 184 the 2-hop neighbor information, Section 5 describes the MDR selection 185 algorithm, Section 6 describes changes to the Interface state 186 machine, section 7 describes the procedures for forming adjacencies 187 and deciding which neighbors should become adjacent, Section 8 188 describes the flooding procedure, Section 9 specifies the 189 requirements and options for the contents of router-LSAs, and Section 190 10 describes changes in the calculation of the routing table. 192 The appendix specifies packet formats, detailed algorithms for the 193 MDR selection algorithm, an algorithm for the selection of a subset 194 of neighbors to advertise in the router-LSA to provide shortest-path 195 routing, a proposed option that uses non-ackable LSAs to provide 196 periodic flooding without the overhead of Link State Acknowledgments, 197 and simulation results that predict the performance of OSPF-MDR in 198 mobile networks with up to 200 nodes. Additional information and 199 resources for OSPF-MDR can be found at http://www.manet-routing.org. 201 1.1. Terminology 203 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 204 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 205 document are to be interpreted as described in [RFC2119]. 207 In addition, this document uses the following terms: 209 MANET Interface 210 A new OSPF interface type that supports broadcast-capable, 211 multihop wireless networks. Two neighboring routers on a MANET 212 interface may not be able to communicate directly with each other. 213 A neighboring router on a MANET interface is called a MANET 214 neighbor. MANET neighbors are discovered dynamically using a 215 modification of OSPF's Hello protocol. 217 MANET Router 218 An OSPF router that has at least one MANET interface. 220 Differential Hello 221 A Hello packet that reduces the overhead of sending full Hellos, 222 by including only the Router IDs of neighbors whose state changed 223 recently. 225 2-Hop Neighbor Information 226 Information that specifies the bidirectional neighbors of each 227 neighbor. The modified Hello protocol provides each MANET router 228 with 2-hop neighbor information, which is used for selecting MDRs 229 and Backup MDRs. 231 MANET Designated Router (MDR) 232 One of a set of routers responsible for flooding new LSAs, and for 233 determining the set of adjacencies that must be formed. The set 234 of MDRs forms a connected dominating set and is a generalization 235 of the DR found in broadcast networks. Each router runs the MDR 236 selection algorithm for each MANET interface, to decide whether 237 the router is an MDR, Backup MDR, or neither for that interface. 239 Backup MANET Designated Router (Backup MDR or BMDR) 240 One of a set of routers responsible for providing backup flooding 241 when neighboring MDRs fail. The set of MDRs and Backup MDRs forms 242 a biconnected dominating set. The Backup MDR is a generalization 243 of the Backup DR found in broadcast networks. 245 MDR Other 246 A router is an MDR Other for a particular MANET interface if it is 247 neither an MDR nor a Backup MDR for that interface. 249 Parent 250 Each router selects a Parent for each MANET interface. The Parent 251 of a non-MDR router will be a neighboring MDR if one exists. The 252 Parent of an MDR is always the router itself. Each non-MDR router 253 becomes adjacent with its Parent. The Router ID of the Parent is 254 advertised in the DR field of each Hello sent on the interface. 256 Backup Parent 257 If the option of biconnected adjacencies is chosen, then each MDR 258 Other selects a Backup Parent, which will be a neighboring MDR or 259 BMDR if one exists that is not the Parent. The Backup Parent of a 260 BMDR is always the router itself. Each MDR Other becomes adjacent 261 with its Backup Parent if it exists. The Router ID of the Backup 262 Parent is advertised in the Backup DR field of each Hello sent on 263 the interface. 265 Bidirectional Neighbor 266 A neighboring router whose neighbor state is 2-Way or greater. 268 Routable Neighbor 269 A bidirectional MANET neighbor becomes routable if the SPF 270 calculation has produced a route to the neighbor and the neighbor 271 satisfies a quality condition. Once a neighbor becomes routable, 272 it remains routable as long as it remains bidirectional. Only 273 routable and Full neighbors can be used as next hops in the SPF 274 calculation, and can be included in the router-LSA originated by 275 the router. 277 Non-flooding MDR 278 An MDR that does not automatically flood received LSAs back out 279 the receiving interface, but performs backup flooding like a BMDR. 280 Some MDRs may declare themselves non-flooding in order to reduce 281 flooding overhead. 283 2. Overview 285 This section provides an overview of OSPF-MDR, including motivation 286 and rationale for some of the design choices. 288 OSPF-MDR was motivated by the desire to extend OSPF to support 289 MANETs, while keeping the same design philosophy as OSPF and using 290 techniques that are similar to those of OSPF. For example, OSPF 291 reduces overhead in a broadcast network by electing a Designated 292 Router (DR) and Backup DR, and by having two neighboring routers form 293 an adjacency only if one of them is the DR or Backup DR. This idea 294 can be generalized to a multihop wireless network by forming a 295 spanning tree, with the edges of the tree being the adjacencies and 296 the interior (non-leaf) nodes of the tree being the generalized DRs, 297 called MANET Designated Routers (MDRs). 299 To provide better robustness and fast response to topology changes, 300 it was decided that a router should decide whether it is an MDR based 301 only on local information that can be obtained from neighbors' 302 Hellos. The resulting set of adjacencies therefore does not always 303 form a tree globally, but appears to be a tree locally. Similarly, 304 the Backup DR can be generalized to Backup MDRs (BMDRs), to provide 305 robustness through biconnected redundancy. The set of MDRs forms a 306 connected dominating set (CDS), and the set of MDRs and BMDRs forms a 307 biconnected dominating set (if the network itself is biconnected). 309 The following subsections provide an overview of each of the main 310 features of OSPF-MDR, starting with a summary of how MDRs, BMDRs, and 311 adjacencies are selected. 313 2.1. Selection of MDRs, BMDRs, Parents, and Adjacencies 315 The MDR selection algorithm is distributed; each router selects 316 itself as an MDR, BMDR, or other router (called an "MDR Other") based 317 on information about its one-hop neighborhood, which is obtained from 318 Hello packets received from neighbors. Routers are ordered 319 lexicographically based on the tuple (RtrPri, MDR Level, RID), where 320 RtrPri is the Router Priority, MDR Level represents the current state 321 of the router (2 for an MDR, 1 for a BMDR, and 0 for an MDR Other), 322 and RID is the Router ID. Routers with lexicographically larger 323 values of (RtrPri, MDR Level, RID) are given preference for becoming 324 MDRs. 326 The MDR selection algorithm can be summarized as follows. If the 327 router itself has a larger value of (RtrPri, MDR Level, RID) than all 328 of its neighbors, it selects itself as an MDR. Otherwise, let Rmax 329 denote the neighbor with the largest value of (RtrPri, MDR Level, 330 RID). The router then selects itself as an MDR unless each neighbor 331 can be reached from Rmax in at most k hops via neighbors that have a 332 larger value of (RtrPri, MDR Level, RID) than the router itself, 333 where k is the parameter MDRConstraint, whose default value is 3. 335 This parameter serves to control the density of the MDR set, since 336 the MDR set need not be strictly minimal. 338 Similarly, a router that does not select itself as an MDR will select 339 itself as a BMDR unless each neighbor can be reached from Rmax via 340 two node-disjoint paths, using as intermediate hops only neighbors 341 that have a larger value of (RtrPri, MDR Level, RID) than the router 342 itself. 344 When a router selects itself as an MDR, it also decides which MDR 345 neighbors it should become adjacent with, to ensure that the set of 346 MDRs and the adjacencies between them form a connected backbone. 347 Each non-MDR router selects and becomes adjacent with an MDR neighbor 348 called its parent, thus ensuring that all routers are connected to 349 the MDR backbone. 351 If the option of biconnected adjacencies is chosen (AdjConnectivity = 352 2), then additional adjacencies are selected to ensure that the set 353 of MDRs and BMDRs, and the adjacencies between them, form a 354 biconnected backbone. In this case, each MDR Other selects and 355 becomes adjacent with an MDR/BMDR neighbor called its backup parent, 356 in addition to its parent. 358 OSPF-MDR also provides the option of full-topology adjacencies 359 (AdjConnectivity = 0). If this option is selected, then each router 360 forms an adjacency with each bidirectional neighbor. Although BMDR 361 selection is optional if AdjConnectivity is 0 or 1, it is recommended 362 since BMDRs improve robustness by providing backup flooding. 364 Prioritizing routers according to (RtrPri, MDR Level, RID) allows 365 neighboring routers to agree on which routers should become an MDR, 366 and gives higher priority to existing MDRs, which increases the 367 lifetime of MDRs and the adjacencies between them. In addition, 368 parents are selected to be existing adjacent neighbors whenever 369 possible, to avoid forming new adjacencies unless necessary. Once a 370 neighbor becomes adjacent, it remains adjacent as long as the 371 neighbor is bidirectional and either the neighbor or the router 372 itself is an MDR or BMDR (similar to OSPF). The above rules reduce 373 the rate at which new adjacencies are formed, which is important 374 since database exchange must be performed whenever a new adjacency is 375 formed. 377 2.2. Flooding Procedure 379 When an MDR receives a new link state advertisement (LSA) on a MANET 380 interface, it floods the LSA back out the receiving interface unless 381 it can be determined that such flooding is unnecessary (as specified 382 in Section 8.1). The router MAY delay the flooding of the LSA by a 383 small random amount of time (e.g., less than 100 ms). The delayed 384 flooding is useful for coalescing multiple LSAs in the same Link 385 State Update packet, and it can reduce the possibility of a collision 386 in case multiple MDRs received the same LSA at the same time. 387 However, such collisions are usually avoided with wireless MAC 388 protocols. 390 When a Backup MDR receives a new LSA on a MANET interface, it waits a 391 short interval (BackupWaitInterval), and then floods the LSA only if 392 it has a neighbor that did not flood or acknowledge the LSA and is 393 not known to be a neighbor of another neighbor (of the Backup MDR) 394 that flooded the LSA. 396 MDR Other routers never flood LSAs back out the receiving interface. 397 To exploit the broadcast nature of MANETs, a new LSA is processed 398 (and possibly forwarded) if it is received from any neighbor in state 399 2-Way or greater. The flooding procedure also avoids redundant 400 forwarding of LSAs when multiple interfaces exist. 402 2.3. Link State Acknowledgments 404 All Link State Acknowledgment packets are multicast. An LSA is 405 acknowledged if it is a new LSA, or if it is a duplicate LSA received 406 as a unicast. (A duplicate LSA received as multicast is not 407 acknowledged.) An LSA that is flooded back out the same interface is 408 treated as an implicit acknowledgment. Link state acknowledgments 409 may be delayed to allow coalescing multiple acknowledgments in the 410 same packet. The only exception is that (Backup) MDRs send a 411 multicast link state acknowledgment immediately when a duplicate LSA 412 is received as a unicast, in order to prevent additional 413 retransmissions. Only link state acknowledgments from adjacent 414 neighbors are processed, and retransmitted LSAs are sent (via 415 unicast) only to adjacent neighbors. 417 2.4. Routable Neighbors 419 In OSPF, a neighbor must typically be fully adjacent (in state Full) 420 for it to be used in the SPF calculation. An exception exists for an 421 OSPF broadcast network, to avoid requiring all pairs of routers in 422 such a network to form adjacencies, which would generate a large 423 amount of overhead. In such a network, a router can use a non- 424 adjacent neighbor as a next hop as long as both routers are fully 425 adjacent with the Designated Router. We define this neighbor 426 relationship as a "routable neighbor" and extend its usage to the 427 MANET interface type. 429 A MANET neighbor becomes routable if it is bidirectional and the SPF 430 calculation has produced a route to the neighbor. (A flexible 431 quality condition may also be required.) Only routable and Full 432 neighbors can be used as next hops in the SPF calculation, and can be 433 included in the router-LSA originated by the router. The idea is 434 that if the SPF calculation has produced a route to the neighbor, 435 then it makes sense to take a "shortcut" and forward packets directly 436 to the neighbor. 438 The routability condition is a generalization of the way that 439 neighbors on broadcast networks are treated in the SPF calculation. 440 The network-LSA of an OSPF broadcast network implies that a router 441 can use a non-adjacent neighbor as a next hop. But a network-LSA 442 cannot describe the general topology of a MANET, making it necessary 443 to explicitly include non-adjacent neighbors in the router-LSA. 444 Allowing only adjacent neighbors in LSAs would either result in 445 suboptimal routes or would require a large number of adjacencies. 447 2.5. Partial and Full Topology LSAs 449 OSPF-MDR allows routers to originate both full-topology LSAs, which 450 advertise links to all routable and Full neighbors, and partial- 451 topology LSAs, which advertise only a subset of such links. In a 452 dense network, partial-topology LSAs are typically much smaller than 453 full-topology LSAs, thus achieving better scalability. 455 Each router advertises a subset of its neighbors as point-to-point 456 links in its router-LSA. The choice of which neighbors to advertise 457 is flexible. As a minimum requirement, each router must advertise a 458 minimum set of "backbone" neighbors in its router-LSA. An LSA that 459 includes only this minimum set of neighbors is called a minimal LSA 460 and corresponds to LSAFullness = 0. This choice results in the 461 minimum amount of LSA flooding overhead, but does not ensure routing 462 along shortest paths. However, it is useful for achieving 463 scalability to networks with a large number of nodes. 465 At the other extreme, if LSAFullness = 4, then the router originates 466 a full-topology LSA, which includes all routable and Full neighbors. 468 Setting LSAFullness to 1 results in min-cost LSAs, which provide 469 routing along shortest (minimum-cost) paths. Each router decides 470 which neighbors to include in its router-LSA based on 2-hop neighbor 471 information obtained from its neighbors' Hellos. Each router 472 includes in its LSA the minimum set of neighbors necessary to provide 473 a shortest path between each pair of its neighbors. 475 Setting LSAFullness to 2 also provides shortest-path routing, but 476 allows the router to advertise additional neighbors to provide 477 redundant routes. 479 Setting LSAFullness to 3 results in MDR full LSAs, causing each MDR 480 to originate a full-topology LSA while other routers originate 481 minimal LSAs. This choice does not provide routing along shortest 482 paths, but simulations have shown that it provides routing along 483 nearly shortest paths with relatively low overhead. 485 The above LSA options are interoperable with each other, because they 486 all require the router-LSA to include a minimum set of neighbors, and 487 because the construction of the router-LSA (described in Section 9.4) 488 ensures that the router-LSAs originated by different routers are 489 consistent. Routing along shortest paths is provided if and only if 490 every router selects LSAFullness to be 1, 2, or 4. 492 2.6. Hello Protocol 494 OSPF-MDR uses the same Hello format as OSPFv3, but appends additional 495 information to Hello packets using link-local signaling (LLS), in 496 order to indicate the set of bidirectional neighbors and other 497 information that is used by the MDR selection algorithm and the min- 498 cost LSA algorithm. In addition to full Hellos, which include the 499 same set of neighbor IDs as OSPFv3 Hellos, OSPF-MDR allows the use of 500 differential Hellos, which include only the IDs of neighbors whose 501 state (or other information) has recently changed (within the last 502 HelloRepeatCount Hellos). 504 Hellos are sent every HelloInterval seconds. Full Hellos are sent 505 every 2HopRefresh Hellos, and differential Hellos are sent at all 506 other times. For example, if 2HopRefresh is equal to 3, then every 507 third Hello is a full Hello. The default value of 2HopRefresh is 1, 508 i.e., the default is to send only full Hellos. The default value for 509 HelloInterval is 2 seconds. Differential Hellos are used to reduce 510 overhead and to allow Hellos to be sent more frequently, for faster 511 reaction to topology changes. 513 3. Interface and Neighbor Data Structures 515 3.1. Changes to Interface Data Structure 517 The following modified or new data items are required for the 518 Interface Data Structure of a MANET interface: 520 Type 521 A router that implements this extension can have one or more 522 interfaces of type MANET, in addition to the OSPF interface types 523 defined in [RFC2328]. 525 State 526 The possible states for a MANET interface are the same as for a 527 broadcast interface. However, the DR and Backup states now imply 528 that the router is an MDR or Backup MDR, respectively. 530 MDR Level 531 The MDR Level is equal to MDR (value 2) if the router is an MDR, 532 Backup MDR (value 1) if the router is a Backup MDR, and MDR Other 533 (value 0) otherwise. The MDR Level is used by the MDR selection 534 algorithm. 536 Parent 537 The Parent replaces the Designated Router (DR) data item of OSPF. 538 Each router selects a Parent as described in Section 5.4. The 539 Parent of an MDR is the router itself, and the Parent of a non-MDR 540 router will be a neighboring MDR, if one exists. The Parent is 541 initialized to 0.0.0.0, indicating the lack of a Parent. Each 542 router advertises the Router ID of its Parent in the DR field of 543 each Hello sent on the interface. 545 Backup Parent 546 The Backup Parent replaces the Backup Designated Router data item 547 of OSPF. The Backup Parent of a BMDR is the router itself. If 548 the option of biconnected adjacencies is chosen, then each MDR 549 Other selects a Backup Parent, which will be a neighboring 550 MDR/BMDR if one exists that is not the Parent. The Backup Parent 551 is initialized to 0.0.0.0, indicating the lack of a Backup Parent. 552 Each router advertises the Router ID of its Backup Parent in the 553 Backup DR field of each Hello sent on the interface. 555 Router Priority 556 An 8-bit unsigned integer. A router with a larger Router Priority 557 is more likely to be selected as an MDR. The Router Priority for 558 a MANET interface can be changed dynamically based on any 559 criteria, including bandwidth capacity, willingness to be a relay 560 (which can depend on battery life, for example), number of 561 neighbors (degree), and neighbor stability. A router that has 562 been a (Backup) MDR for a certain amount of time can reduce its 563 Router Priority so that the burden of being a (Backup) MDR can be 564 shared among all routers. If the Router Priority for a MANET 565 interface is changed, then the interface variable 566 MDRNeighborChange must be set. 568 Hello Sequence Number (HSN) 569 The 16-bit sequence number carried by the MDR-Hello TLV. The HSN 570 is incremented by 1 (modulo 2^16) every time a Hello packet is 571 sent on the interface. 573 MDRNeighborChange 574 A single-bit variable set to 1 if a neighbor change has occurred 575 that requires the MDR selection algorithm to be executed. 577 3.2. New Configurable Interface Parameters 579 The following new configurable interface parameters are required for 580 a MANET interface. The default values for HelloInterval, 581 RouterDeadInterval, and RxmtInterval for a MANET interface are 2, 6, 582 and 7 seconds, respectively. 584 The default configuration for OSPF-MDR uses uniconnected adjacencies 585 (AdjConnectivity = 1) and partial-topology LSAs that provide 586 shortest-path routing (LSAFullness = 1). This is the most scalable 587 configuration that provides shortest-path routing. Other 588 configurations may be preferable in special circumstances. For 589 example, setting LSAFullness to 4 provides full-topology LSAs, and 590 setting LSAFullness to 0 provides minimal LSAs that minimize overhead 591 but do not ensure shortest-path routing. Setting AdjConnectivity to 592 2 may improve robustness by providing a biconnected adjacency 593 subgraph, and setting AdjConnectivity to 0 results in full-topology 594 adjacencies. 596 All possible configurations of the new interface parameters are 597 functional, except that if AdjConnectivity is 0 (full-topology 598 adjacencies), then LSAFullness must be 1, 2, or 4 (see Section 9.3). 600 Differential Hellos should be used to reduce the size of Hello 601 packets when the average number of neighbors is large (e.g., greater 602 than 50). Differential Hellos are obtained by setting the parameter 603 2HopRefresh to an integer greater than 1, with the recommended value 604 being 3. Good performance in simulated mobile networks with up to 605 160 nodes has been obtained using the default configuration with 606 differential Hellos. Good performance in simulated mobile networks 607 with up to 200 nodes has been obtained using the same configuration 608 except with minimal LSAs (LSAFullness = 0). Simulation results are 609 presented in Appendix E. 611 Although all routers should preferably choose the same values for the 612 new configurable interface parameters, this is not required. OSPF- 613 MDR was carefully designed so that correct interoperation is achieved 614 even if each router sets these parameters independently of the other 615 routers. 617 AdjConnectivity 618 If equal to the default value of 1, then the set of adjacencies 619 forms a (uni)connected graph. If equal to the optional value of 620 2, then the set of adjacencies forms a biconnected graph. If 621 AdjConnectivity is 0, then adjacency reduction is not used, i.e., 622 the router becomes adjacent with all of its neighbors. 624 MDRConstraint 625 A parameter of the MDR selection algorithm, which affects the 626 number of MDRs selected and must be an integer greater than or 627 equal to 2. The default value of 3 results in nearly the minimum 628 number of MDRs. Values larger than 3 result in slightly fewer 629 MDRs, and the value 2 results in a larger number of MDRs. 631 BackupWaitInterval 632 The number of seconds that a Backup MDR must wait after receiving 633 a new LSA, before it decides whether to flood the LSA. The 634 default value is 0.5 second. 636 AckInterval 637 The interval between Link State Acknowledgment packets when only 638 delayed acknowledgments need to be sent. AckInterval MUST be less 639 than RxmtInterval, and SHOULD NOT be larger than 1 second. The 640 default value is 1 second. 642 LSAFullness 643 Determines which neighbors a router should advertise in its 644 router-LSA. The value 0 results in minimal LSAs that include only 645 "backbone" neighbors. The values 1 and 2 result in partial- 646 topology LSAs that provide shortest-path routing, with the value 2 647 providing redundant routes. The value 3 results in MDRs 648 originating full-topology LSAs and other routers originating 649 minimal LSAs. The value 4 results in all routers originating 650 full-topology LSAs. The default value is 1. 652 2HopRefresh 653 One out of every 2HopRefresh Hellos sent on the interface must be 654 a full Hello. All other Hellos are differential. The default 655 value is 1, i.e., the default is to send only full Hellos. If 656 differential Hellos are used, the recommended value of 2HopRefresh 657 is 3. 659 HelloRepeatCount 660 The number of consecutive Hellos in which a neighbor must be 661 included when its state changes, if differential Hellos are used. 662 This parameter must be set to 3. 664 3.3. Changes to Neighbor Data Structure 666 The neighbor states are the same as for OSPF. However, the data for 667 a MANET neighbor that has transitioned to the Down state must be 668 maintained for at least HelloInterval * HelloRepeatCount seconds, to 669 allow the state change to be reported in differential Hellos. The 670 following new data items are required for the Neighbor Data Structure 671 of a neighbor on a MANET interface. 673 Neighbor Hello Sequence Number (NHSN) 674 The Hello sequence number contained in the last Hello received 675 from the neighbor. 677 A-bit 678 The A-bit copied from the MDR-Hello TLV of the last Hello received 679 from the neighbor. This bit is 1 if the neighbor is using full- 680 topology adjacencies, i.e., is not using adjacency reduction. 682 FullHelloRcvd 683 A single-bit variable equal to 1 if a full Hello has been received 684 from the neighbor. 686 Neighbor's MDR Level 687 The MDR Level of the neighbor, based on the DR and Backup DR 688 fields of the last Hello packet received from the neighbor or from 689 the MDR-DD TLV in a DD packet received from the neighbor. 691 Neighbor's Parent 692 The neighbor's choice for Parent, obtained from the DR field of 693 the last Hello packet received from the neighbor or from the MDR- 694 DD TLV in a DD packet received from the neighbor. 696 Neighbor's Backup Parent 697 The neighbor's choice for Backup Parent, obtained from the Backup 698 DR field of the last Hello packet received from the neighbor or 699 from the MDR-DD TLV in a DD packet received from the neighbor. 701 Child 702 A single-bit variable equal to 1 if the neighbor is a child, i.e., 703 if the neighbor has selected the router as a (Backup) Parent. 705 Dependent Neighbor 706 A single-bit variable equal to 1 if the neighbor is a Dependent 707 Neighbor, which is decided by the MDR selection algorithm. Each 708 MDR/BMDR router becomes adjacent with its Dependent Neighbors 709 (which are also MDR/BMDR routers) to form a connected backbone. 710 The set of all Dependent Neighbors on a MANET interface is called 711 the Dependent Neighbor Set (DNS) for the interface. 713 Dependent Selector 714 A single-bit variable equal to 1 if the neighbor has selected the 715 router to be Dependent. 717 Selected Advertised Neighbor (SAN) 718 A single-bit variable equal to 1 if the neighbor is a selected 719 advertised neighbor. Selected advertised neighbors are neighbors 720 that the router has selected to be included in the router-LSA, 721 along with other neighbors that are required to be included. The 722 set of all selected advertised neighbors on a MANET interface is 723 called the Selected Advertised Neighbor Set (SANS) for the 724 interface. 726 Routable 727 A single-bit variable equal to 1 if the neighbor is routable. 729 Neighbor's Bidirectional Neighbor Set (BNS) 730 The neighbor's set of bidirectional neighbors, which is updated 731 when a Hello is received from the neighbor. 733 Neighbor's Dependent Neighbor Set (DNS) 734 The neighbor's set of Dependent Neighbors, which is updated when a 735 Hello is received from the neighbor. 737 Neighbor's Selected Advertised Neighbor Set (SANS) 738 The neighbor's set of Selected Advertised Neighbors, which is 739 updated when a Hello is received from the neighbor. 741 Neighbor's Link Metrics 742 The link metric for each of the neighbor's bidirectional 743 neighbors, obtained from the Metric TLV appended to Hello packets. 745 4. Hello Protocol 747 The MANET interface utilizes Hellos for neighbor discovery and for 748 enabling neighbors to learn 2-hop neighbor information. The protocol 749 is flexible because it allows the use of full or differential Hellos. 750 Full Hellos list all neighbors on the interface that are in state 751 Init or greater, as in OSPFv3, whereas differential Hellos list only 752 neighbors whose status as a bidirectional neighbor, Dependent 753 Neighbor, or Selected Advertised Neighbor has recently changed. 754 Differential Hellos are used to reduce overhead, and they allow 755 Hellos to be sent more frequently (for faster reaction to topology 756 changes). If differential Hellos are used, full Hellos are sent less 757 frequently to ensure that all neighbors have current 2-hop neighbor 758 information. 760 4.1. Sending Hello Packets 762 Hello packets are sent according to [RFC5340] Section 4.2.1.1 and 763 [RFC2328] Section 9.5 with the following MANET specific 764 specifications beginning after paragraph 3 of Section 9.5. The Hello 765 packet format is defined in [RFC5340] Section A.3.2, except for the 766 ordering of the Neighbor IDs and the meaning of the DR and Backup DR 767 fields as described below. 769 Similar to [RFC2328], the DR and Backup DR fields indicate whether 770 the router is an MDR or Backup MDR. If the router is an MDR, then 771 the DR field is the router's own Router ID, and if the router is a 772 Backup MDR, then the Backup DR field is the router's own Router ID. 773 These fields are also used to advertise the router's Parent and 774 Backup Parent, as specified in Section A.3 and Section 5.4. 776 Hellos are sent every HelloInterval seconds. Full Hellos are sent 777 every 2HopRefresh Hellos, and differential Hellos are sent at all 778 other times. For example, if 2HopRefresh is equal to 3, then every 779 third Hello is a full Hello. If 2HopRefresh is set to 1, then all 780 Hellos are full (the default). 782 The neighbor IDs included in the body of each Hello are divided into 783 the following five disjoint lists of neighbors (some of which may be 784 empty), and must appear in the following order: 786 List 1. Neighbors whose state recently changed to Down (included 787 only in differential Hellos). 788 List 2. Neighbors in state Init. 789 List 3. Dependent Neighbors. 790 List 4. Selected Advertised Neighbors. 791 List 5. Unselected bidirectional neighbors, defined as bidirectional 792 neighbors that are neither Dependent nor Selected Advertised 793 Neighbors. 795 Note that all neighbors in Lists 3 through 5 are bidirectional 796 neighbors. These lists are used to update the neighbor's 797 Bidirectional Neighbor Set (BNS), Dependent Neighbor Set (DNS), and 798 Selected Advertised Neighbor Set (SANS) when a Hello is received. 800 Note that the above five lists are disjoint, so each neighbor can 801 appear in at most one list. Also note that some or all of the five 802 lists can be empty. 804 Link-local signaling (LLS) is used to append up to two TLVs to each 805 MANET Hello packet. The format for LLS is given in Section A.2. The 806 MDR-Hello TLV is appended to each (full or differential) MANET Hello 807 packet. It indicates whether the Hello is full or differential, and 808 gives the Hello Sequence Number (HSN) and the number of neighbor IDs 809 in each of Lists 1 through 4 defined above. The size of List 5 is 810 then implied by the packet length field of the Hello. The format of 811 the MDR-Hello TLV is given in Section A.2.3. 813 In both full and differential Hellos, the appended MDR-Hello TLV is 814 built as follows. 816 o The Sequence Number field is set to the current HSN for the 817 interface; the HSN is then incremented (modulo 2^16). 819 o The D-bit of the MDR-Hello TLV is set to 1 for a differential 820 Hello and 0 for a full Hello. 822 o The A-bit of the MDR-Hello TLV is set to 1 if AdjConnectivity is 0 823 (the router is using full-topology adjacencies); otherwise it is 824 set to 0. 826 o The N1, N2, N3, and N4 fields are set to the number of neighbor 827 IDs in the body of the Hello that are in List 1, List 2, List 3, 828 and List 4, respectively. (N1 is always zero in a full Hello.) 830 The MDR-Metric TLV (or Metric TLV) advertises the link cost to each 831 bidirectional neighbor on the interface, to allow the selection of 832 neighbors to include in partial-topology LSAs. If LSAFullness is 1 833 or 2, a Metric TLV must be appended to each MANET Hello packet unless 834 all link costs are 1. The format of the Metric TLV is given in 835 Section A.2.5. The I bit of the Metric TLV can be set to 0 or 1. If 836 the I bit is set to 0, then the Metric TLV does not contain neighbor 837 IDs, and contains the metric for each bidirectional neighbor listed 838 in the (full or differential) Hello, in the same order. If the I bit 839 is set to 1, then the Metric TLV includes the neighbor ID and metric 840 for each bidirectional neighbor listed in the Hello whose metric is 841 not equal to the Default Metric field of the TLV. 843 The I bit should be chosen to minimize the size of the Metric TLV. 844 This can be achieved by choosing the I bit to be 1 if and only if the 845 number of bidirectional neighbors listed in the Hello whose metric 846 differs from the Default Metric field is less than 1/3 of the total 847 number of bidirectional neighbors listed in the Hello. 849 For example, if all neighbors have the same metric, then the I bit 850 should be set to 1, with the Default Metric equal to this metric, 851 avoiding the need to include neighbor IDs and corresponding metrics 852 in the TLV. At the other extreme, if all neighbors have different 853 metrics, then the I bit should be set to 0 to avoid listing the same 854 neighbor IDs in both the body of the Hello and the Metric TLV. 856 In both full and differential Hello packets, the L bit is set in the 857 Hello's option field to indicate LLS. 859 4.1.1. Full Hello Packet 861 In a full Hello, the neighbor ID list includes all neighbors on the 862 interface that are in state Init or greater, in the order described 863 above. The MDR-Hello TLV is built as described above. If a Metric 864 TLV is appended, it is built as specified in Section A.2.5. 866 4.1.2. Differential Hello Packet 868 In a differential Hello, the five neighbor ID lists defined in 869 Section 4.1 are populated as follows: 871 List 1 includes each neighbor in state Down that has not yet been 872 included in HelloRepeatCount Hellos since transitioning to this 873 state. 875 List 2 includes each neighbor in state Init that has not yet been 876 included in HelloRepeatCount Hellos since transitioning to this 877 state. 879 List 3 includes each Dependent Neighbor that has not yet been 880 included in HelloRepeatCount Hellos since becoming a Dependent 881 Neighbor. 883 List 4 includes each Selected Advertised Neighbor that has not yet 884 been included in HelloRepeatCount Hellos since becoming a Selected 885 Advertised Neighbor. 887 List 5 includes each unselected bidirectional neighbor (defined in 888 Section 4.1) that has not yet been included in HelloRepeatCount 889 Hellos since becoming an unselected bidirectional neighbor. 891 In addition, a bidirectional neighbor must be included (in the 892 appropriate list) if the neighbor's BNS does not include the router 893 (indicating that the neighbor does not consider the router to be 894 bidirectional). 896 If a Metric TLV is appended to the Hello, then a bidirectional 897 neighbor must be included (in the appropriate list) if it has not yet 898 been included in HelloRepeatCount Hellos since its metric last 899 changed. 901 4.2. Receiving Hello Packets 903 A Hello packet received on a MANET interface is processed as 904 described in [RFC5340] Section 4.2.2.1 and the first two paragraphs 905 of [RFC2328] Section 10.5, followed by the processing specified 906 below. 908 The source of a received Hello packet is identified by the Router ID 909 found in the Hello's OSPF packet header. If a matching neighbor 910 cannot be found in the interface's data structure, one is created 911 with the Neighbor ID set to the Router ID found in the OSPF packet 912 header, the state initialized to Down, all MANET-specific neighbor 913 variables (specified in Section 3.3) initialized to zero, and the 914 neighbor's DNS, SANS, and BNS initialized to empty sets. 916 The neighbor structure's Router Priority is set to the value of the 917 corresponding field in the received Hello packet. The Neighbor's 918 Parent is set to the value of the DR field, and the Neighbor's Backup 919 Parent is set to the value of the Backup DR field. 921 Now the rest of the Hello Packet is examined, generating events to be 922 given to the neighbor and interface state machines. These state 923 machines are specified either to be executed or scheduled (see 924 [RFC2328] Section 4.4 "Tasking support"). For example, by specifying 925 below that the neighbor state machine be executed in line, several 926 neighbor state transitions may be affected by a single received 927 Hello. 929 o If the L bit in the options field is not set, then an error has 930 occurred and the Hello is discarded. 932 o If the LLS contains a MDR-Hello TLV, the neighbor state machine is 933 executed with the event HelloReceived. Otherwise, an error has 934 occurred and the Hello is discarded. 936 o The Hello Sequence Number and the A-bit in the MDR-Hello TLV are 937 copied to the neighbor's data structure. 939 o The DR and Backup DR fields are processed as follows. 941 (1) If the DR field is equal to the neighbor's Router ID, 942 set the neighbor's MDR Level to MDR. 944 (2) Else if the Backup DR field is equal to the neighbor's 945 Router ID, set the neighbor's MDR Level to Backup MDR. 947 (3) Else, set the neighbor's MDR Level to MDR Other and set the 948 neighbor's Dependent Neighbor variable to 0. (Only MDR/BMDR 949 neighbors can be Dependent.) 951 (4) If the DR or Backup DR field is equal to the router's own 952 Router ID, set the neighbor's Child variable to 1; otherwise 953 set it to 0. 955 The neighbor ID list of the Hello is divided as follows into the five 956 lists defined in Section 4.1, where N1, N2, N3, and N4 are obtained 957 from the corresponding fields of the MDR-Hello TLV. List 1 is 958 defined to be the first N1 neighbor IDs, List 2 is defined to be the 959 next N2 neighbor IDs, List 3 is defined to be the next N3 neighbor 960 IDs, List 4 is defined to be the next N4 neighbor IDs, and List 5 is 961 defined to be the remaining neighbor IDs in the Hello. 963 Further processing of the Hello depends on whether it is full or 964 differential, which is indicated by the value of the D-bit of the 965 MDR-Hello TLV. 967 4.2.1. Full Hello Packet 969 If the received Hello is full (the D-bit of the MDR-Hello TLV is 0), 970 the following steps are performed: 972 o If the N1 field of the MDR-Hello TLV is not zero, then an error 973 has occurred and the Hello is discarded. Otherwise, set 974 FullHelloRcvd to 1. 976 o In the neighbor structure, modify the neighbor's DNS to equal the 977 set of neighbor IDs in the Hello's List 3, modify the neighbor's 978 SANS to equal the set of neighbor IDs in the Hello's List 4, and 979 modify the neighbor's BNS to equal the set of neighbor IDs in the 980 union of Lists 3, 4, and 5. 982 o If the router itself appears in the Hello's neighbor ID list, the 983 neighbor state machine is executed with the event 2-WayReceived 984 after the Hello is processed. Otherwise, the neighbor state 985 machine is executed with the event 1-WayReceived after the Hello 986 is processed. 988 4.2.2. Differential Hello Packet 990 If the received Hello is differential (the D-bit of the MDR-Hello TLV 991 is 1), the following steps are performed: 993 (1) For each neighbor ID in List 1 or List 2 of the Hello: 995 o Remove the neighbor ID from the neighbor's DNS, SANS, 996 and BNS, if it belongs to the neighbor set. 998 (2) For each neighbor ID in List 3 of the Hello: 1000 o Add the neighbor ID to the neighbor's DNS and BNS, if it 1001 does not belong to the neighbor set. 1003 o Remove the neighbor ID from the neighbor's SANS, if it 1004 belongs to the neighbor set. 1006 (3) For each neighbor ID in List 4 of the Hello: 1008 o Add the neighbor ID to the neighbor's SANS and BNS, if it 1009 does not belong to the neighbor set. 1011 o Remove the neighbor ID from the neighbor's DNS, if it 1012 belongs to the neighbor set. 1014 (4) For each neighbor ID in List 5 of the Hello: 1016 o Add the neighbor ID to the neighbor's BNS, if it does not 1017 belong to the neighbor set. 1019 o Remove the neighbor ID from the neighbor's DNS and SANS, if 1020 it belongs to the neighbor set. 1022 (5) If the router's own RID appears in List 1, execute the neighbor 1023 state machine with the event 1-WayReceived after the Hello is 1024 processed. 1026 (6) If the router's own RID appears in List 2, 3, 4, or 5, execute 1027 the neighbor state machine with the event 2-WayReceived after 1028 the Hello is processed. 1030 (7) If the router's own RID does not appear in the Hello's neighbor 1031 ID list, and the neighbor state is 2-Way or greater, and the 1032 Hello Sequence Number is less than or equal to the previous 1033 sequence number plus HelloRepeatCount, then the neighbor state 1034 machine is executed with the event 2-WayReceived after the Hello 1035 is processed (the state does not change). 1037 (8) If 2-WayReceived is not executed, then 1-WayReceived is executed 1038 after the Hello is processed. 1040 4.2.3. Additional Processing for Both Hello Types 1042 The following applies to both full and differential Hellos. 1044 If the router itself belongs to the neighbor's DNS, the neighbor's 1045 Dependent Selector variable is set to 1; otherwise it is set to 0. 1047 The receiving interface's MDRNeighborChange variable is set to 1 if 1048 any of the following changes occurred as a result of processing the 1049 Hello: 1051 o The neighbor's state changed from less than 2-Way to 2-Way or 1052 greater, or vice versa. 1054 o The neighbor is bidirectional and any of the following neighbor 1055 variables has changed: MDR Level, Router Priority, FullHelloRcvd, 1056 and Bidirectional Neighbor Set (BNS). 1058 The neighbor state machine is scheduled with the event AdjOK? if any 1059 of the following changes occurred as a result of processing the 1060 Hello: 1062 o The neighbor's state changed from less than 2-Way to 2-Way or 1063 greater. 1065 o The neighbor is bidirectional and its MDR Level has changed, or 1066 its Child variable or Dependent Selector variable has changed from 1067 0 to 1. 1069 If the LLS contains a Metric TLV, it is processed by updating the 1070 neighbor's link metrics according to the format of the Metric TLV 1071 specified in Section A.2.5. If the LLS does not contain a Metric TLV 1072 and LSAFullness is 1 or 2, the metric for each of the neighbor's 1073 links is set to 1. 1075 4.3. Neighbor Acceptance Condition 1077 In wireless networks, a single Hello can be received from a neighbor 1078 with which a poor connection exists, e.g., because the neighbor is 1079 almost out of range. To avoid accepting poor quality neighbors, and 1080 to employ hysteresis, a router may require that a stricter condition 1081 be satisfied before changing the state of a MANET neighbor from Down 1082 to Init or greater. This condition is called the "neighbor 1083 acceptance condition", which by default is the reception of a single 1084 Hello or DD packet. For example, the neighbor acceptance condition 1085 may require that 2 consecutive Hellos be received from a neighbor 1086 before changing the neighbor's state from Down to Init. Other 1087 possible conditions include the reception of 3 consecutive Hellos, or 1088 the reception of 2 of the last 3 Hellos. The neighbor acceptance 1089 condition may also impose thresholds on other measurements such as 1090 received signal strength. 1092 The neighbor state transition for state Down and event HelloReceived 1093 is thus modified (see Section 7.1) to depend on the neighbor 1094 acceptance condition. 1096 5. MDR Selection Algorithm 1098 This section describes the MDR selection algorithm, which is run for 1099 each MANET interface to determine whether the router is an MDR, 1100 Backup MDR, or MDR Other for that interface. The algorithm also 1101 selects the Dependent Neighbors and the (Backup) Parent, which are 1102 used to decide which neighbors should become adjacent (see Section 1103 7.2). 1105 The MDR selection algorithm must be executed just before sending a 1106 Hello if the MDRNeighborChange bit is set for the interface. The 1107 algorithm SHOULD also be executed whenever a bidirectional neighbor 1108 transitions to less than 2-Way, and MAY be executed at other times 1109 when the MDRNeighborChange bit is set. The bit is cleared after the 1110 algorithm is executed. 1112 To simplify the implementation, the MDR selection algorithm MAY be 1113 executed periodically just before sending each Hello, to avoid having 1114 to determine when the MDRNeighborChange bit should be set. After 1115 running the MDR selection algorithm, the AdjOK? event may be invoked 1116 for some or all neighbors as specified in Section 7. 1118 The purpose of the MDRs is to provide a minimal set of relays for 1119 flooding LSAs, and the purpose of the Backup MDRs is to provide 1120 backup relays to flood LSAs when flooding by MDRs does not succeed. 1121 The set of MDRs forms a CDS, and the set of MDRs and Backup MDRs 1122 forms a biconnected CDS (if the network itself is biconnected). 1124 Each MDR selects and becomes adjacent with a subset of its MDR 1125 neighbors, called Dependent Neighbors, forming a connected backbone. 1126 Each non-MDR router connects to this backbone by selecting and 1127 becoming adjacent with an MDR neighbor called its Parent. Each MDR 1128 selects itself as Parent, to inform neighbors that it is an MDR. 1130 If AdjConnectivity = 2, then each (Backup) MDR selects and becomes 1131 adjacent with additional (Backup) MDR neighbors to form a biconnected 1132 backbone, and each MDR Other selects and becomes adjacent with a 1133 second (Backup) MDR neighbor called its Backup Parent, thus becoming 1134 connected to the backbone via two adjacencies. Each BMDR selects 1135 itself as Backup Parent, to inform neighbors that it is a BMDR. 1137 The MDR selection algorithm is a distributed CDS algorithm that uses 1138 2-hop neighbor information obtained from Hellos. More specifically, 1139 it uses as inputs the set of bidirectional neighbors (in state 2-Way 1140 or greater), the triplet (Router Priority, MDR Level, Router ID) for 1141 each such neighbor and for the router itself, and the neighbor 1142 variables Bidirectional Neighbor Set (BNS) and FullHelloRcvd for each 1143 such neighbor. The MDR selection algorithm can be implemented in 1144 O(d^2) time, where d is the number of neighbors. 1146 The above triplet will be abbreviated as (RtrPri, MDR Level, RID). 1147 The triplet (RtrPri, MDR Level, RID) is said to be larger for Router 1148 A than for Router B if the triplet for Router A is lexicographically 1149 greater than the triplet for Router B. Routers that have larger 1150 values of this triplet are preferred for selection as an MDR. The 1151 algorithm therefore prefers routers that are already MDRs, resulting 1152 in a longer average MDR lifetime. 1154 The MDR selection algorithm consists of five phases, the last of 1155 which is optional. Phase 1 creates the neighbor connectivity matrix 1156 for the interface, which determines which pairs of neighbors are 1157 neighbors of each other. Phase 2 decides whether the calculating 1158 router is an MDR, and which MDR neighbors are Dependent. Phase 3 1159 decides whether the calculating router is a Backup MDR and, if 1160 AdjConnectivity = 2, which additional MDR/BMDR neighbors are 1161 Dependent. Phase 4 selects the Parent and Backup Parent. 1163 The algorithm simplifies considerably if AdjConnectivity is 0 (full- 1164 topology adjacencies). In this case, the set of Dependent Neighbors 1165 is empty and MDR Other routers need not select parents. Also, Phase 1166 3 (BMDR selection) is not required if AdjConnectivity is 0 or 1. 1167 However, Phase 3 MUST be executed if AdjConnectivity is 2, and SHOULD 1168 be executed if AdjConnectivity is 0 or 1, since BMDRs improve 1169 robustness by providing backup flooding. 1171 A router that has selected itself as an MDR in Phase 2 MAY execute 1172 Phase 5 to possibly declare itself a non-flooding MDR. A non- 1173 flooding MDR is the same as a flooding MDR except that it does not 1174 automatically flood received LSAs back out the receiving interface, 1175 because it has determined that neighboring MDRs are sufficient to 1176 flood the LSA to all neighbors. Instead, a non-flooding MDR performs 1177 backup flooding just like a BMDR. A non-flooding MDR maintains its 1178 MDR level (rather than being demoted to a BMDR) in order to maximize 1179 the stability of adjacencies. (The decision to form an adjacency 1180 does not depend on whether an MDR is non-flooding.) By having MDRs 1181 declare themselves to be non-flooding when possible, flooding 1182 overhead is reduced. The resulting reduction in flooding overhead 1183 can be dramatic for certain regular topologies, but has been found to 1184 be less than 15% for random topologies. 1186 The following subsections describe the MDR selection algorithm, which 1187 is applied independently to each MANET interface. For convenience, 1188 the term "bi-neighbor" will be used as an abbreviation for 1189 "bidirectional neighbor". 1191 5.1. Phase 1: Creating the Neighbor Connectivity Matrix 1193 Phase 1 creates the neighbor connectivity matrix (NCM) for the 1194 interface. The NCM is a symmetric matrix that defines a topology 1195 graph for the set of bi-neighbors on the interface. The NCM assigns 1196 a value of 0 or 1 for each pair of bi-neighbors; a value of 1 1197 indicates that the neighbors are assumed to be bi-neighbors of each 1198 other in the MDR selection algorithm. Letting i denote the router 1199 itself, NCM(i,j) and NCM(j,i) are set to 1 for each bi-neighbor j. 1200 The value of the matrix is set as follows for each pair of bi- 1201 neighbors j and k on the interface. 1203 (1.1) If FullHelloRcvd is 1 for both neighbors j and k: NCM(j,k) = 1204 NCM(k,j) is 1 only if j belongs to the BNS of neighbor k and k 1205 belongs to the BNS of neighbor j. 1207 (1.2) If FullHelloRcvd is 1 for neighbor j and is 0 for neighbor k: 1208 NCM(j,k) = NCM(k,j) is 1 only if k belongs to the BNS of 1209 neighbor j. 1211 (1.3) If FullHelloRcvd is 0 for both neighbors j and k: NCM(j,k) = 1212 NCM(k,j) = 0. 1214 In Step 1.1 above, two neighbors are considered to be bi-neighbors of 1215 each other only if they both agree that the other router is a bi- 1216 neighbor. This provides faster response to the failure of a link 1217 between two neighbors, since it is likely that one router will detect 1218 the failure before the other router. In Step 1.2 above, only 1219 neighbor j has reported its full BNS, so neighbor j is believed in 1220 deciding whether j and k are bi-neighbors of each other. As Step 1.3 1221 indicates, two neighbors are assumed not to be bi-neighbors of each 1222 other if neither neighbor has reported its full BNS. 1224 5.2. Phase 2: MDR Selection 1226 Phase 2 depends on the parameter MDRConstraint, which affects the 1227 number of MDRs selected. The default value of 3 results in nearly 1228 the minimum number of MDRs, while the value 2 results in a larger 1229 number of MDRs. If AdjConnectivity = 0 (full-topology adjacencies), 1230 then the following steps are modified in that Dependent Neighbors are 1231 not selected. 1233 (2.1) The set of Dependent Neighbors is initialized to be empty. 1235 (2.2) If the router has a larger value of (RtrPri, MDR Level, RID) 1236 than all of its bi-neighbors, the router selects itself as an 1237 MDR; selects all of its MDR bi-neighbors as Dependent 1238 Neighbors; if AdjConnectivity = 2, selects all of its BMDR bi- 1239 neighbors as Dependent Neighbors; then proceeds to Phase 4. 1241 (2.3) Let Rmax be the bi-neighbor with the largest value of (RtrPri, 1242 MDR Level, RID). 1244 (2.4) Using NCM to determine the connectivity of bi-neighbors, 1245 compute the minimum number of hops, denoted hops(u), from Rmax 1246 to each other bi-neighbor u, using only intermediate nodes that 1247 are bi-neighbors with a larger value of (RtrPri, MDR Level, 1248 RID) than the router itself. If no such path from Rmax to u 1249 exists, then hops(u) equals infinity. (See Appendix B for a 1250 detailed algorithm using breadth-first search.) 1252 (2.5) If hops(u) is at most MDRConstraint for each bi-neighbor u, the 1253 router selects no Dependent Neighbors, and sets its MDR Level 1254 as follows: If the MDR Level is currently MDR, then it is 1255 changed to BMDR if Phase 3 will be executed and to MDR Other if 1256 Phase 3 will not be executed. Otherwise, the MDR Level is not 1257 changed. 1259 (2.6) Else, the router sets its MDR Level to MDR and selects the 1260 following neighbors as Dependent Neighbors: Rmax if it is an 1261 MDR or BMDR; each MDR bi-neighbor u such that hops(u) is 1262 greater than MDRConstraint; and if AdjConnectivity = 2, each 1263 BMDR bi-neighbor u such that hops(u) is greater than 1264 MDRConstraint. 1266 (2.7) If steps 2.1 through 2.6 resulted in the MDR Level changing to 1267 BMDR, or to MDR with AdjConnectivity equal to 1 or 2, then 1268 execute steps 2.1 through 2.6 again. (This is necessary 1269 because the change in MDR Level can cause the set of Dependent 1270 Neighbors and the BFS tree to change.) This step is not 1271 required if the MDR selection algorithm is executed 1272 periodically. 1274 Step 2.4 can be implemented using a breadth-first search (BFS) 1275 algorithm to compute min-hop paths from Rmax to all other bi- 1276 neighbors, modified to allow a bi-neighbor to be an intermediate node 1277 only if its value of (RtrPri, MDR Level, RID) is larger than that of 1278 the router itself. A detailed description of this algorithm, which 1279 runs in O(d^2) time, is given in Appendix B. 1281 5.3. Phase 3: Backup MDR Selection 1283 (3.1) If the MDR Level is MDR (after running Phase 2) and 1284 AdjConnectivity is not 2, then proceed to Phase 4. (If the MDR 1285 Level is MDR and AdjConnectivity = 2, then Phase 3 may select 1286 additional Dependent Neighbors to create a biconnected 1287 backbone.) 1289 (3.2) Using NCM to determine the connectivity of bi-neighbors, 1290 determine whether or not there exist two node-disjoint paths 1291 from Rmax to each other bi-neighbor u, using only intermediate 1292 nodes that are bi-neighbors with a larger value of (RtrPri, MDR 1293 Level, RID) than the router itself. (See Appendix B for a 1294 detailed algorithm.) 1296 (3.3) If there exist two such node-disjoint paths from Rmax to each 1297 other bi-neighbor u, then the router selects no additional 1298 Dependent Neighbors and sets its MDR Level to MDR Other. 1300 (3.4) Else, the router sets its MDR Level to Backup MDR unless it 1301 already selected itself as an MDR in Phase 2, and if 1302 AdjConnectivity = 2, adds each of the following neighbors to 1303 the set of Dependent Neighbors: Rmax if it is an MDR or BMDR, 1304 and each MDR/BMDR bi-neighbor u such that Step 3.2 did not find 1305 two node-disjoint paths from Rmax to u. 1307 (3.5) If steps 3.1 through 3.4 resulted in the MDR Level changing 1308 from MDR Other to BMDR, then run Phases 2 and 3 again. (This 1309 is necessary because running Phase 2 again can cause the MDR 1310 Level to change to MDR.) This step is not required if the MDR 1311 selection algorithm is executed periodically. 1313 Step 3.2 can be implemented in O(d^2) time using the algorithm given 1314 in Appendix B. A simplified version of the algorithm is also 1315 specified, which results in a larger number of BMDRs. 1317 5.4. Phase 4: Parent Selection 1319 Each router selects a Parent for each MANET interface. The Parent of 1320 a non-MDR router will be a neighboring MDR if one exists. If the 1321 option of biconnected adjacencies is chosen, then each MDR Other 1322 selects a Backup Parent, which will be a neighboring MDR/BMDR if one 1323 exists that is not the Parent. The Parent of an MDR is always the 1324 router itself, and the Backup Parent of a BMDR is always the router 1325 itself. 1327 The (Backup) Parent is advertised in the (Backup) DR field of each 1328 Hello sent on the interface. As specified in Section 7.2, each 1329 router forms an adjacency with its Parent and Backup Parent if it 1330 exists and is a neighboring MDR/BMDR. 1332 For a given MANET interface, let Rmax denote the router with the 1333 largest value of (RtrPri, MDR Level, RID) among all bidirectional 1334 neighbors, if such a neighbor exists that has a larger value of 1335 (RtrPri, MDR Level, RID) than the router itself. Otherwise, Rmax is 1336 null. 1338 If the calculating router has selected itself as an MDR, then the 1339 Parent is equal to the router itself, and the Backup Parent is Rmax. 1340 (The latter design choice was made because it results in slightly 1341 better performance than choosing no Backup Parent.) If the router 1342 has selected itself as a BMDR, then the Backup Parent is equal to the 1343 router itself. 1345 If the calculating router is a BMDR or MDR Other, the Parent is 1346 selected to be any adjacent neighbor that is an MDR, if such a 1347 neighbor exists. If no adjacent MDR neighbor exists, then the Parent 1348 is selected to be Rmax. By giving preference to neighbors that are 1349 already adjacent, the formation of a new adjacency is avoided when 1350 possible. Note that the Parent can be a non-MDR neighbor temporarily 1351 when no MDR neighbor exists. (This design choice was also made for 1352 performance reasons.) 1354 If AdjConnectivity = 2 and the calculating router is an MDR Other, 1355 then the Backup Parent is selected to be any adjacent neighbor that 1356 is an MDR or BMDR, other than the Parent selected in the previous 1357 paragraph, if such a neighbor exists. If no such adjacent neighbor 1358 exists, then the Backup Parent is selected to be the bidirectional 1359 neighbor, excluding the selected Parent, with the largest value of 1360 (RtrPri, MDR Level, RID), if such a neighbor exists. Otherwise, the 1361 Backup Parent is null. 1363 5.5. Phase 5: Optional Selection of Non-Flooding MDRs 1365 A router that has selected itself as an MDR MAY execute the following 1366 steps to possibly declare itself a non-flooding MDR. An MDR that 1367 does not execute the following steps is by default a flooding MDR. 1369 (5.1) If the router has a larger value of (RtrPri, MDR Level, RID) 1370 than all of its bi-neighbors, the router is a flooding MDR. Else, 1371 proceed to Step 5.2. 1373 (5.2) Let Rmax be the bi-neighbor that has the largest value of 1374 (RtrPri, MDR Level, RID). 1376 (5.3) Using NCM to determine the connectivity of bi-neighbors, 1377 compute the minimum number of hops, denoted hops(u), from Rmax to 1378 each other bi-neighbor u, using only intermediate nodes that are MDR 1379 bi-neighbors with a smaller value of (RtrPri, RID) than the router 1380 itself. (This can be done using BFS as in Step 2.4). 1382 (5.4) If hops(u) is at most MDRConstraint for each bi-neighbor u, 1383 then the router is a non-flooding MDR. Else, it is a flooding MDR. 1385 6. Interface State Machine 1387 6.1. Interface States 1389 No new states are defined for a MANET interface. However, the DR and 1390 Backup states now imply that the router is an MDR or Backup MDR, 1391 respectively. The following modified definitions apply to MANET 1392 interfaces: 1394 Waiting 1395 In this state, the router learns neighbor information from the 1396 Hello packets it receives, but is not allowed to run the MDR 1397 selection algorithm until it transitions out of the Waiting state 1398 (when the Wait Timer expires). This prevents unnecessary changes 1399 in the MDR selection resulting from incomplete neighbor 1400 information. The length of the Wait Timer is 2HopRefresh * 1401 HelloInterval seconds (the interval between full Hellos). 1403 DR Other 1404 The router has run the MDR selection algorithm and determined that 1405 it is not an MDR or a Backup MDR. 1407 Backup 1408 The router has selected itself as a Backup MDR. 1410 DR 1411 The router has selected itself as an MDR. 1413 6.2. Events that Cause Interface State Changes 1415 All interface events defined in [RFC2328] Section 9.2 apply to MANET 1416 interfaces, except for BackupSeen and NeighborChange. BackupSeen is 1417 never invoked for a MANET interface (since seeing a Backup MDR does 1418 not imply that the router itself cannot also be an MDR or Backup 1419 MDR). 1421 The event NeighborChange is replaced with the new interface variable 1422 MDRNeighborChange, which indicates that the MDR selection algorithm 1423 must be executed due to a change in neighbor information (see Section 1424 4.2.3). 1426 6.3. Changes to Interface State Machine 1428 This section describes the changes to the interface state machine for 1429 a MANET interface. The two state transitions specified below are for 1430 state-event pairs that are described in [RFC2328], but have modified 1431 action descriptions because MDRs are selected instead of DRs. The 1432 state transition in [RFC2328] for the event NeighborChange is 1433 omitted; instead the new interface variable MDRNeighborChange is used 1434 to indicate when the MDR selection algorithm needs to be executed. 1435 The state transition for the event BackupSeen does not apply to MANET 1436 interfaces, since this event is never invoked for a MANET interface. 1437 The interface state transitions for the events Loopback and UnloopInd 1438 are unchanged from [RFC2328]. 1440 State: Down 1441 Event: InterfaceUp 1442 New state: Depends on action routine. 1444 Action: Start the interval Hello Timer, enabling the periodic 1445 sending of Hello packets out the interface. The state 1446 transitions to Waiting and the single shot Wait Timer 1447 is started. 1449 State: Waiting 1450 Event: WaitTimer 1451 New state: Depends on action routine. 1453 Action: Run the MDR selection algorithm, which may result in a 1454 change to the router's MDR Level, Dependent Neighbors, 1455 and (Backup) Parent. As a result of this calculation, 1456 the new interface state will be DR Other, Backup, or DR. 1458 As a result of these changes, the AdjOK? neighbor event 1459 may be invoked for some or all neighbors. (See 1460 Section 7.) 1462 7. Adjacency Maintenance 1464 Adjacency forming and eliminating on non-MANET interfaces remain 1465 unchanged. Adjacency maintenance on a MANET interface requires 1466 changes to transitions in the neighbor state machine ([RFC2328] 1467 Section 10.3), to deciding whether to become adjacent ([RFC2328] 1468 Section 10.4), sending of DD packets ([RFC2328] Section 10.8), and 1469 receiving of DD packets ([RFC2328] Section 10.6). The specification 1470 below relates to the MANET interface only. 1472 If full-topology adjacencies are used (AdjConnectivity = 0), the 1473 router forms an adjacency with each bidirectional neighbor. If 1474 adjacency reduction is used (AdjConnectivity is 1 or 2), the router 1475 forms adjacencies with a subset of its neighbors, according to the 1476 rules specified in Section 7.2. 1478 An adjacency maintenance decision is made when any of the following 1479 four events occur between a router and its neighbor. The decision is 1480 made by executing the neighbor event AdjOK?. 1482 (1) The neighbor state changes from Init to 2-Way. 1483 (2) The MDR Level changes for the neighbor or for the router itself. 1484 (3) The neighbor is selected to be the (Backup) Parent. 1485 (4) The neighbor selects the router to be its (Backup) Parent. 1487 7.1. Changes to Neighbor State Machine 1489 The following specifies new transitions in the neighbor state 1490 machine. 1492 State(s): Down 1493 Event: HelloReceived 1494 New state: Depends on action routine. 1496 Action: If the neighbor acceptance condition is satisfied (see 1497 Section 4.3), the neighbor state transitions to Init and 1498 the Inactivity Timer is started. Otherwise, the neighbor 1499 remains in the Down state. 1501 State(s): Init 1502 Event: 2-WayReceived 1503 New state: 2-Way 1505 Action: Transition to neighbor state 2-Way. 1507 State(s): 2-Way 1508 Event: AdjOK? 1509 New state: Depends on action routine. 1511 Action: Determine whether an adjacency should be formed with the 1512 neighboring router (see Section 7.2). If not, the 1513 neighbor state remains at 2-Way and no further action is 1514 taken. 1516 Otherwise, the neighbor state changes to ExStart, and the 1517 following actions are performed. If the neighbor has a 1518 larger Router ID than the router's own ID, and the 1519 received packet is a DD packet with the initialize (I), 1520 more (M), and master (MS) bits set, then execute the 1521 event NegotiationDone, which causes the state to 1522 transition to Exchange. 1524 Otherwise (negotiation is not complete), the router 1525 increments the DD sequence number in the neighbor data 1526 structure. If this is the first time that an adjacency 1527 has been attempted, the DD sequence number should be 1528 assigned a unique value (like the time of day clock). It 1529 then declares itself master (sets the master/slave bit to 1530 master), and starts sending Database Description Packets, 1531 with the initialize (I), more (M) and master (MS) bits 1532 set, the MDR-DD TLV included in an LLS, and the L bit 1533 set. This Database Description Packet should be 1534 otherwise empty. This Database Description Packet should 1535 be retransmitted at intervals of RxmtInterval until the 1536 next state is entered (see [RFC2328] Section 10.8). 1538 State(s): ExStart or greater 1539 Event: AdjOK? 1540 New state: Depends on action routine. 1542 Action: Determine whether the neighboring router should still be 1543 adjacent (see Section 7.3). If yes, there is no state 1544 change and no further action is necessary. Otherwise, 1545 the (possibly partially formed) adjacency must be 1546 destroyed. The neighbor state transitions to 2-Way. The 1547 Link state retransmission list, Database summary list, 1548 and Link state request list are cleared of LSAs. 1550 7.2. Whether to Become Adjacent 1552 The following defines the method to determine if an adjacency should 1553 be formed between neighbors in state 2-Way. The following procedure 1554 does not depend on whether AdjConnectivity is 1 or 2, but the 1555 selection of Dependent Neighbors (by the MDR selection algorithm) 1556 depends on AdjConnectivity. 1558 If adjacency reduction is not used (AdjConnectivity = 0), then an 1559 adjacency is formed with each neighbor in state 2-Way. Otherwise an 1560 adjacency is formed with a neighbor in state 2-Way if any of the 1561 following conditions is true: 1563 (1) The router is a (Backup) MDR and the neighbor is a (Backup) 1564 MDR and is either a Dependent Neighbor or a Dependent Selector. 1566 (2) The neighbor is a (Backup) MDR and is the router's (Backup) 1567 Parent. 1569 (3) The router is a (Backup) MDR and the neighbor is a child. 1571 (4) The neighbor's A-bit is 1, indicating the neighbor is using 1572 full-topology adjacencies. 1574 Otherwise, an adjacency is not established and the neighbor remains 1575 in state 2-Way. 1577 7.3. Whether to Eliminate an Adjacency 1579 The following defines the method to determine if an existing 1580 adjacency should be eliminated. An existing adjacency is maintained 1581 if any of the following is true: 1583 (1) The router is an MDR or Backup MDR. 1585 (2) The neighbor is an MDR or Backup MDR. 1587 (3) The neighbor's A-bit is 1, indicating the neighbor is using 1588 full-topology adjacencies. 1590 Otherwise, the adjacency MAY be eliminated. 1592 7.4. Sending Database Description Packets 1594 Sending a DD packet on a MANET interface is the same as [RFC5340] 1595 Section 4.2.1.2 and [RFC2328] Section 10.8 with the following 1596 additions to paragraph 3 of Section 10.8. 1598 If the neighbor state is ExStart, the standard initialization packet 1599 is sent with an MDR-DD TLV appended using LLS, and the L bit is set 1600 in the DD packet's option field. The format for the MDR-DD TLV is 1601 specified in Section A.2.4. The DR and Backup DR fields of the MDR- 1602 DD TLV are set exactly the same as the DR and Backup DR fields of a 1603 Hello sent on the same interface. 1605 7.5. Receiving Database Description Packets 1607 Processing a DD packet received on a MANET interface is the same as 1608 [RFC2328] Section 10.6, except for the changes described in this 1609 section. The following additional steps are performed before 1610 processing the packet based on neighbor state in paragraph 3 of 1611 Section 10.6. 1613 o If the DD packet's L bit is set in the options field and an MDR-DD 1614 TLV is appended, then the MDR-DD TLV is processed as follows. 1616 (1) If the DR field is equal to the neighbor's Router ID: 1617 (a) Set the MDR Level of the neighbor to MDR. 1618 (b) Set the neighbor's Dependent Selector variable to 1. 1620 (2) Else if the Backup DR field is equal to the neighbor's 1621 Router ID: 1622 (a) Set the MDR Level of the neighbor to Backup MDR. 1623 (b) Set the neighbor's Dependent Selector variable to 1. 1625 (3) Else: 1626 (a) Set the MDR Level of the neighbor to MDR Other. 1627 (b) Set the neighbor's Dependent Neighbor variable to 0. 1629 (4) If the DR or Backup DR field is equal to the router's own 1630 Router ID, set the neighbor's Child variable to 1; otherwise 1631 set it to 0. 1633 o If the neighbor state is Init, the neighbor event 2-WayReceived is 1634 executed. 1636 o If the MDR Level of the neighbor changed, the neighbor state 1637 machine is scheduled with the event AdjOK?. 1639 o If the neighbor's Child status has changed from 0 to 1, the 1640 neighbor state machine is scheduled with the event AdjOK?. 1642 o If the neighbor's neighbor state changed from less than 2-Way to 1643 2-Way or greater, the neighbor state machine is scheduled with the 1644 event AdjOK?. 1646 In addition, the Database Exchange optimization described in 1647 [RFC5243] SHOULD be performed as follows. If the router accepts a 1648 received DD packet as the next in sequence, the following additional 1649 step should be performed for each LSA listed in the DD packet 1650 (whether the router is master or slave). If the Database summary 1651 list contains an instance of the LSA that is the same as or less 1652 recent than the listed LSA, the LSA is removed from the Database 1653 summary list. This avoids listing the LSA in a DD packet sent to the 1654 neighbor, when the neighbor already has an instance of the LSA that 1655 is the same or more recent. This optimization reduces overhead due 1656 to DD packets by approximately 50% in large networks. 1658 8. Flooding Procedure 1660 This section specifies the changes to [RFC2328] Section 13 for 1661 routers that support OSPF-MDR. The first part of Section 13 (before 1662 Section 13.1) is the same except for the following three changes. 1664 o To exploit the broadcast nature of MANETs, if the Link State 1665 Update (LSU) packet was received on a MANET interface, then the 1666 packet is dropped without further processing only if the sending 1667 neighbor is in a lesser state than 2-Way. Otherwise, the LSU 1668 packet is processed as described in this section. 1670 o If the received LSA is the same instance as the database copy, the 1671 following actions are performed in addition to Step 7. For each 1672 MANET interface for which a BackupWait Neighbor List exists for 1673 the LSA (see Section 8.1): 1675 (a) Remove the sending neighbor from the BackupWait Neighbor List 1676 if it belongs to the list. 1677 (b) For each neighbor on the receiving interface that belongs 1678 to the BNS for the sending neighbor, remove the neighbor 1679 from the BackupWait Neighbor List if it belongs to the list. 1681 o Step 8, which handles the case in which the database copy of the 1682 LSA is more recent than the received LSA, is modified as follows. 1683 If the sending neighbor is in a lesser state than Exchange, then 1684 the router does not send the LSA back to the sending neighbor. 1686 There are no changes to Sections 13.1, 13.2, or 13.4. The following 1687 subsections describe the changes to Sections 13.3 (Next step in the 1688 flooding procedure), 13.5 (Sending Link State Acknowledgments), 13.6 1689 (Retransmitting LSAs), and 13.7 (Receiving Link State 1690 Acknowledgments) of [RFC2328]. 1692 8.1. LSA Forwarding Procedure 1694 When a new LSA is received, Steps 1 through 5 of [RFC2328] Section 1695 13.3 are performed without modification for each eligible (outgoing) 1696 interface that is not of type MANET. This section specifies the 1697 modified steps that must be performed for each eligible MANET 1698 interface. The eligible interfaces depend on the LSA's flooding 1699 scope as described in [RFC5340] Section 4.5.2. Whenever an LSA is 1700 flooded out a MANET interface, it is included in an LSU packet that 1701 is sent to the multicast address AllSPFRouters. (Retransmitted LSAs 1702 are always unicast, as specified in Section 8.3.) 1704 Step 1 of [RFC2328] Section 13.3 is performed for each eligible MANET 1705 interface with the following modification, so that the new LSA is 1706 placed on the Link State retransmission list for each appropriate 1707 adjacent neighbor. Step 1c is replaced with the following action, so 1708 that the LSA is not placed on the retransmission list for a neighbor 1709 that has already acknowledged the LSA. 1711 o If the new LSA was received from this neighbor, or a link state 1712 acknowledgment (LS Ack) for the new LSA has already been received 1713 from this neighbor, examine the next neighbor. 1715 To determine whether an Ack for the new LSA has been received from 1716 the neighbor, the router maintains an Acked LSA List for each 1717 adjacent neighbor, as described in Section 8.4. When a new LSA is 1718 received, the Acked LSA List for each neighbor, on each MANET 1719 interface, should be updated by removing any LS Ack that is for an 1720 older instance of the LSA than the one received. 1722 The following description will use the notion of a "covered" 1723 neighbor. A neighbor k is defined to be covered if the LSA was sent 1724 as a multicast by a MANET neighbor j, and neighbor k belongs to the 1725 Bidirectional Neighbor Set (BNS) for neighbor j. A neighbor k is 1726 also defined to be covered if the LSA was sent to the multicast 1727 address AllSPFRouters by a neighbor j on a broadcast interface on 1728 which both j and k are neighbors. (Note that j must be the DR or 1729 Backup DR for the broadcast network, since only these routers may 1730 send LSAs to AllSPFRouters on a broadcast network.) 1732 The following steps must be performed for each eligible MANET 1733 interface, to determine whether the new LSA should be forwarded on 1734 the interface. 1736 (2) If every bidirectional neighbor on the interface satisfies at 1737 least one of the following three conditions, examine the next 1738 interface (the LSA is not flooded out this interface). 1740 (a) The LSA was received from the neighbor. 1742 (b) The LSA was received on a MANET or broadcast interface and 1743 the neighbor is covered (defined above). 1745 (c) An Ack for the LSA has been received from the neighbor. 1747 Condition (c) MAY be omitted (thus ignoring Acks) in order to 1748 simplify this step. Note that the above conditions do not assume 1749 the outgoing interface is the same as the receiving interface. 1751 (3) If the LSA was received on this interface, and the router is an 1752 MDR Other for this interface, examine the next interface (the LSA 1753 is not flooded out this interface). 1755 (4) If the LSA was received on this interface, and the router is a 1756 Backup MDR or a non-flooding MDR for this interface, then the 1757 router waits BackupWaitInterval before deciding whether to flood 1758 the LSA. To accomplish this, the router creates a BackupWait 1759 Neighbor List for the LSA, which initially includes every 1760 bidirectional neighbor on this interface that does not satisfy 1761 any of the conditions in Step 2. A single shot BackupWait Timer 1762 associated with the LSA is started, which is set to expire after 1763 BackupWaitInterval seconds plus a small amount of random jitter. 1764 (The actions performed when the BackupWait Timer expires are 1765 described below in Section 8.1.2.) Examine the next interface 1766 (the LSA is not yet flooded out this interface). 1768 (5) If the router is a flooding MDR for this interface, or if the LSA 1769 was originated by the router itself, then the LSA is flooded out 1770 the interface (whether or not the LSA was received on this 1771 interface) and the next interface is examined. 1773 (6) If the LSA was received on a MANET or broadcast interface that is 1774 different from this (outgoing) interface, then the following two 1775 steps SHOULD be performed to avoid redundant flooding. 1777 (a) If the router has a larger value of (RtrPri, MDR Level, RID) 1778 on the outgoing interface than every covered neighbor 1779 (defined above) that is a neighbor on BOTH the receiving and 1780 outgoing interfaces (or if no such neighbor exists), then the 1781 LSA is flooded out the interface and the next interface is 1782 examined. 1784 (b) Else, the router waits BackupWaitInterval before deciding 1785 whether to flood the LSA on the interface, by performing the 1786 actions in Step 4 for a Backup MDR (whether or not the router 1787 is a Backup MDR on this interface). A separate BackupWait 1788 Neighbor List is created for each MANET interface, but only 1789 one BackupWait Timer is associated with the LSA. Examine the 1790 next interface (the LSA is not yet flooded out this 1791 interface). 1793 (7) If this step is reached, the LSA is flooded out the interface. 1795 8.1.1. Note on Step 6 of LSA Forwarding Procedure 1797 Performing the optional Step 6 can greatly reduce flooding overhead 1798 if the LSA was received on a MANET or broadcast interface. For 1799 example, assume the LSA was received from the DR of a broadcast 1800 network that includes 100 routers, and 50 of the routers (not 1801 including the DR) are also attached to a MANET. Assume that these 50 1802 routers are neighbors of each other in the MANET, and that each has a 1803 neighbor in the MANET that is not attached to the broadcast network 1804 (and is therefore not covered). Then by performing Step 6 of the LSA 1805 forwarding procedure, the number of routers that forward the LSA from 1806 the broadcast network to the MANET is reduced from 50 to just 1 1807 (assuming that at most one of the 50 routers is an MDR). 1809 8.1.2. BackupWait Timer Expiration 1811 If the BackupWait Timer for an LSA expires, then the following steps 1812 are performed for each (MANET) interface for which a BackupWait 1813 Neighbor List exists for the LSA. 1815 (1) If the BackupWait Neighbor List for the interface contains at 1816 least one router that is currently a bidirectional neighbor, the 1817 following actions are performed. 1819 (a) The LSA is flooded out the interface. 1821 (b) If the LSA is on the Ack List for the interface (i.e., is 1822 scheduled to be included in a delayed Link State 1823 Acknowledgment packet), then the router SHOULD remove the LSA 1824 from the Ack List, since the flooded LSA will be treated as 1825 an implicit Ack. 1827 (c) If the LSA is on the Link State retransmission list for any 1828 neighbor, the retransmission SHOULD be rescheduled to occur 1829 after RxmtInterval seconds. 1831 (2) The BackupWait Neighbor List is then deleted (whether or not the 1832 LSA is flooded). 1834 8.2. Sending Link State Acknowledgments 1836 This section describes the procedure for sending Link State 1837 Acknowledgments (LS Acks) on MANET interfaces. Section 13.5 of 1838 [RFC2328] remains unchanged for non-MANET interfaces, but does not 1839 apply to MANET interfaces. To minimize overhead due to LS Acks, and 1840 to take advantage of the broadcast nature of MANETs, all LS Ack 1841 packets sent on a MANET interface are multicast using the IP address 1842 AllSPFRouters. In addition, duplicate LSAs received as a multicast 1843 are not acknowledged. 1845 When a router receives an LSA, it must decide whether to send a 1846 delayed Ack, an immediate Ack, or no Ack. The interface parameter 1847 AckInterval is the interval between LS Ack packets when only delayed 1848 Acks need to be sent. A delayed Ack SHOULD be delayed by at least 1849 (RxmtInterval - AckInterval - 0.5) seconds and at most (RxmtInterval 1850 - 0.5) seconds after the LSA instance being acknowledged was first 1851 received. If AckInterval and RxmtInterval are equal to their default 1852 values of 1 and 7 seconds, respectively, this reduces Ack traffic by 1853 increasing the chance that a new instance of the LSA will be received 1854 before the delayed Ack is sent. An immediate Ack is sent immediately 1855 in a multicast LS Ack packet, which may also include delayed Acks 1856 that were scheduled to be sent. 1858 The decision whether to send a delayed or immediate Ack depends on 1859 whether the received LSA is new (i.e., is more recent than the 1860 database copy) or a duplicate (the same instance as the database 1861 copy), and on whether the LSA was received as a multicast or a 1862 unicast (which indicates a retransmitted LSA). The following rules 1863 are used to make this decision. 1865 (1) If the received LSA is new, a delayed Ack is sent on each 1866 MANET interface associated with the area, unless the LSA is 1867 flooded out the interface. 1869 (2) If the LSA is a duplicate and was received as a multicast, 1870 the LSA is not acknowledged. 1872 (3) If the LSA is a duplicate and was received as a unicast: 1874 (a) If the router is an MDR, or AdjConnectivity = 2 and the 1875 router is a Backup MDR, or AdjConnectivity = 0, then an 1876 immediate Ack is sent out the receiving interface. 1878 (b) Otherwise, a delayed Ack is sent out the receiving 1879 interface. 1881 The reason that (Backup) MDRs send an immediate Ack when a 1882 retransmitted LSA is received, is to try to prevent other adjacent 1883 neighbors from retransmitting the LSA, since (Backup) MDRs usually 1884 have a large number of adjacent neighbors. MDR Other routers do not 1885 send an immediate Ack (unless AdjConnectivity = 0) because they have 1886 fewer adjacent neighbors, and so the potential benefit does not 1887 justify the additional overhead resulting from sending immediate 1888 Acks. 1890 8.3. Retransmitting LSAs 1892 LSAs are retransmitted according to Section 13.6 of [RFC2328]. Thus, 1893 LSAs are retransmitted only to adjacent routers. Therefore, since 1894 OSPF-MDR does not allow an adjacency to be formed between two MDR 1895 Other routers, an MDR Other never retransmits an LSA to another MDR 1896 Other, only to its parents, which are (Backup) MDRs. 1898 Retransmitted LSAs are included in LSU packets that are unicast 1899 directly to an adjacent neighbor that did not acknowledge the LSA 1900 (explicitly or implicitly). The length of time between 1901 retransmissions is given by the configurable interface parameter 1902 RxmtInterval, whose default is 7 seconds for a MANET interface. To 1903 reduce overhead, several retransmitted LSAs should be included in a 1904 single LSU packet whenever possible. 1906 8.4. Receiving Link State Acknowledgments 1908 A Link State Acknowledgment (LS Ack) packet that is received from an 1909 adjacent neighbor (in state Exchange or greater) is processed as 1910 described in Section 13.7 of [RFC2328], with the additional steps 1911 described in this section. An LS Ack packet that is received from a 1912 neighbor in a lesser state than Exchange is discarded. 1914 Each router maintains an Acked LSA List for each adjacent neighbor, 1915 to keep track of any LSA instances the neighbor has acknowledged, but 1916 which the router itself has NOT yet received. This is necessary 1917 because (unlike [RFC2328]) each router acknowledges an LSA only the 1918 first time it is received as a multicast. 1920 If the neighbor from which the LS Ack packet was received is in state 1921 Exchange or greater, then the following steps are performed for each 1922 LS Ack in the received LS Ack packet: 1924 (1) If the router does not have a database copy of the LSA being 1925 acknowledged, or has a database copy that is less recent than the 1926 one being acknowledged, the LS Ack is added to the Acked LSA List 1927 for the sending neighbor. 1929 (2) If the router has a database copy of the LSA being acknowledged, 1930 which is the same as the instance being acknowledged, then the 1931 following action is performed. For each MANET interface for 1932 which a BackupWait Neighbor List exists for the LSA (see Section 1933 8.1), remove the sending neighbor from the BackupWait Neighbor 1934 List if it belongs to the list. 1936 9. Router-LSAs 1938 Unlike the DR of an OSPF broadcast network, an MDR does not originate 1939 a network-LSA, since a network-LSA cannot be used to describe the 1940 general topology of a MANET. Instead, each router advertises a 1941 subset of its MANET neighbors as point-to-point links in its router- 1942 LSA. The choice of which MANET neighbors to include in the router- 1943 LSA is flexible. Whether or not adjacency reduction is used, the 1944 router can originate either partial-topology or full-topology LSAs. 1946 If adjacency reduction is used (AdjConnectivity is 1 or 2), then as a 1947 minimum requirement each router must advertise a minimum set of 1948 "backbone" neighbors in its router-LSA. This minimum choice 1949 corresponds to LSAFullness = 0, and results in the minimum amount of 1950 LSA flooding overhead, but does not provide routing along shortest 1951 paths. 1953 Therefore, to allow routers to calculate shortest paths, without 1954 requiring every pair of neighboring routers along the shortest paths 1955 to be adjacent (which would be inefficient due to requiring a large 1956 number of adjacencies), a router-LSA may also advertise non-adjacent 1957 neighbors that satisfy a synchronization condition described below. 1959 To motivate this, we note that OSPF already allows a non-adjacent 1960 neighbor to be a next hop, if both the router and the neighbor belong 1961 to the same broadcast network (and are both adjacent to the DR). A 1962 network-LSA for a broadcast network (which includes all routers 1963 attached to the network) implies that any router attached to the 1964 network can forward packets directly to any other router attached to 1965 the network (which is why the distance from the network to all 1966 attached routers is zero in the graph representing the link-state 1967 database). 1969 Since a network-LSA cannot be used to describe the general topology 1970 of a MANET, the only way to advertise non-adjacent neighbors that can 1971 be used as next hops, is to include them in the router-LSA. However, 1972 to ensure that such neighbors are sufficiently synchronized, only 1973 "routable" neighbors are allowed to be included in LSAs, and to be 1974 used as next hops in the SPF calculation. 1976 9.1. Routable Neighbors 1978 If adjacency reduction is used, a bidirectional MANET neighbor 1979 becomes routable if the SPF calculation has found a route to the 1980 neighbor and the neighbor satisfies the routable neighbor quality 1981 condition (defined below). Since only routable and Full neighbors 1982 are advertised in router-LSAs, and since adjacencies are selected to 1983 form a connected spanning subgraph, this definition implies that 1984 there exists, or recently existed, a path of full adjacencies from 1985 the router to the routable neighbor. The idea is that, since a 1986 routable neighbor can be reached through an acceptable path, it makes 1987 sense to take a "shortcut" and forward packets directly to the 1988 routable neighbor. 1990 This requirement does not guarantee perfect synchronization, but 1991 simulations have shown that it performs well in mobile networks. 1992 This requirement avoids, for example, forwarding packets to a new 1993 neighbor that is poorly synchronized because it was not reachable 1994 before it became a neighbor. 1996 To avoid selecting poor quality neighbors as routable neighbors, a 1997 neighbor that is selected as a routable neighbor must satisfy the 1998 routable neighbor quality condition. By default, this condition is 1999 that the neighbor's BNS must include the router itself (indicating 2000 that the neighbor agrees the connection is bidirectional). 2001 Optionally, a router may impose a stricter condition. For example, a 2002 router may require that two Hellos have been received from the 2003 neighbor that (explicitly or implicitly) indicate that the neighbor's 2004 BNS includes the router itself. 2006 The single-bit neighbor variable Routable indicates whether the 2007 neighbor is routable, and is initially set to 0. If adjacency 2008 reduction is used, Routable is updated as follows when the state of 2009 the neighbor changes, or the SPF calculation finds a route to the 2010 neighbor, or a Hello is received that affects the routable neighbor 2011 quality condition. 2013 (1) If Routable is 0 for the neighbor, the state of the neighbor is 2014 2-Way or greater, there exists a route to the neighbor, and the 2015 routable neighbor quality condition (defined above) is satisfied, 2016 then Routable is set to 1 for the neighbor. 2018 (2) If Routable is 1 for the neighbor and the state of the neighbor 2019 is less than 2-Way, Routable is set to 0 for the neighbor. 2021 If adjacency reduction is not used (AdjConnectivity = 0), then 2022 routable neighbors are not computed and the set of routable neighbors 2023 remains empty. 2025 9.2. Backbone Neighbors 2027 The flexible choice for the router-LSA is made possible by defining 2028 two types of neighbors that are included in the router-LSA: backbone 2029 neighbors and selected advertised neighbors. 2031 If adjacency reduction is used, a bidirectional neighbor is defined 2032 to be a backbone neighbor if and only if it satisfies the condition 2033 for becoming adjacent (see Section 7.2). If adjacency reduction is 2034 not used (AdjConnectivity = 0), a bidirectional neighbor is a 2035 backbone neighbor if and only if the neighbor's A-bit is 0 2036 (indicating the neighbor is using adjacency reduction). This 2037 definition allows the interoperation between routers that use 2038 adjacency reduction and routers that do not. 2040 If adjacency reduction is used, then a router MUST include in its 2041 router-LSA all Full neighbors and all routable backbone neighbors. A 2042 minimal LSA, corresponding to LSAFullness = 0, includes only these 2043 neighbors. This choice guarantees connectivity, but does not ensure 2044 shortest paths. However, this choice is useful in large networks to 2045 achieve maximum scalability. 2047 9.3. Selected Advertised Neighbors 2049 To allow flexibility while ensuring that router-LSAs are symmetric 2050 (i.e., router i advertises a link to router j if and only if router j 2051 advertises a link to router i), each router maintains a selected 2052 advertised neighbor set (SANS), which consists of MANET neighbors 2053 that the router has selected to advertise in its router-LSA, not 2054 including backbone neighbors. Since the SANS does not include 2055 backbone neighbors (and thus Dependent Neighbors), the SANS and DNS 2056 are disjoint. Both of these neighbor sets are advertised in Hellos. 2058 If LSAFullness is 0 (minimal LSAs), then the SANS is empty. At the 2059 other extreme, if LSAFullness is 4 (full-topology LSAs), the SANS 2060 includes all bidirectional MANET neighbors except backbone neighbors. 2061 In between these two extremes, a router that is using adjacency 2062 reduction may select any subset of bidirectional non-backbone 2063 neighbors as its SANS. The resulting router-LSA is constructed as 2064 specified in Section 9.4. 2066 Since a router that is not using adjacency reduction typically has no 2067 backbone neighbors (unless it has neighbors that are using adjacency 2068 reduction), to ensure connectivity, such a router must choose its 2069 SANS to contain the SANS corresponding to LSAFullness = 1. Thus, if 2070 AdjConnectivity is 0 (no adjacency reduction), then LSAFullness must 2071 be 1, 2, or 4. 2073 If LSAFullness is 1, the router originates min-cost LSAs, which are 2074 partial-topology LSAs that (when flooded) provide each router with 2075 sufficient information to calculate a shortest (minimum-cost) path to 2076 each destination. Appendix C describes the algorithm for selecting 2077 the neighbors to include in the SANS that results in min-cost LSAs. 2078 The input to this algorithm includes information obtained from Hellos 2079 received from each MANET neighbor, including the neighbor's 2080 Bidirectional Neighbor Set (BNS), Dependent Neighbor Set (DNS), 2081 Selected Advertised Neighbor Set (SANS), and the Metric TLV. The 2082 Metric TLV, specified in Section A.2.5, is appended to each Hello 2083 (unless all link costs are 1) to advertise the link cost to each 2084 bidirectional neighbor. 2086 If LSAFullness is 2, the SANS must be selected to be a superset of 2087 the SANS corresponding to LSAFullness = 1. This choice provides 2088 shortest-path routing while allowing the router to advertise 2089 additional neighbors to provide redundant routes. 2091 If LSAFullness is 3, each MDR originates a full-topology LSA (which 2092 includes all Full and routable neighbors), while each non-MDR router 2093 originates a minimal LSA. If the router has multiple MANET 2094 interfaces, the router-LSA includes all Full and routable neighbors 2095 on each interface for which it is an MDR, and advertises only Full 2096 neighbors and routable backbone neighbors on its other interfaces. 2097 This choice provides routing along nearly shortest paths with 2098 relatively low overhead. 2100 Although this document specifies a few choices of the SANS, which 2101 correspond to different values of LSAFullness, it is important to 2102 note that other choices are possible. In addition, it is not 2103 necessary for different routers to choose the same value of 2104 LSAFullness. The different choices are interoperable because they 2105 all require the router-LSA to include a minimum set of neighbors, and 2106 because the construction of the router-LSA (described below) ensures 2107 that the router-LSAs originated by different routers are consistent. 2109 9.4. Originating Router-LSAs 2111 When a new router-LSA is originated, it includes a point-to-point 2112 (type 1) link for each MANET neighbor that is advertised. The set of 2113 neighbors to be advertised is determined as follows. If adjacency 2114 reduction is used, the router advertises all Full neighbors, and 2115 advertises each routable neighbor j that satisfies any of the 2116 following three conditions. If adjacency reduction is not used 2117 (AdjConnectivity = 0), the router advertises each Full neighbor j 2118 that satisfies any of the following three conditions. 2120 (1) The router's SANS (for any interface) includes j. 2122 (2) Neighbor j's SANS includes the router (to ensure symmetry). 2124 (3) Neighbor j is a backbone neighbor. 2126 Note that backbone neighbors and neighbors in the SANS need not be 2127 routable or Full, but only routable and Full neighbors may be 2128 included in the router-LSA. This is done so that the SANS, which is 2129 advertised in Hellos, does not depend on routability. 2131 The events that cause a new router-LSA to be originated are the same 2132 as in [RFC2328] and [RFC5340] except that a MANET neighbor changing 2133 to/from the Full state does not always cause a new router-LSA to be 2134 originated. Instead, a new router-LSA is originated whenever a 2135 change occurs that causes any of the following three conditions to 2136 occur: 2138 o There exists a MANET neighbor j that satisfies the above 2139 conditions for inclusion in the router-LSA, but is not included in 2140 the current router-LSA. 2142 o The current router-LSA includes a MANET neighbor that is no longer 2143 bidirectional. 2145 o The link metric has changed for a MANET neighbor that is included 2146 in the current router-LSA. 2148 The above conditions may be checked periodically just before sending 2149 each Hello, instead of checking them every time one of the neighbor 2150 sets changes. The following implementation was found to work well. 2151 Just before sending each Hello, and whenever a bidirectional neighbor 2152 transitions to less than 2-Way, the router runs the MDR selection 2153 algorithm, updates its adjacencies, routable neighbors, and selected 2154 advertised neighbors, then checks the above conditions to see if a 2155 new router-LSA should be originated. In addition, if a neighbor 2156 becomes bidirectional or Full, the router updates its routable 2157 neighbors and checks the above conditions. 2159 10. Calculating the Routing Table 2161 The routing table calculation is the same as specified in [RFC2328], 2162 except for the following changes to Section 16.1 (Calculating the 2163 shortest-path tree for an area). If full-topology adjacencies and 2164 full-topology LSAs are used (AdjConnectivity = 0 and LSAFullness = 2165 4), there is no change to Section 16.1. 2167 If adjacency reduction is used (AdjConnectivity is 1 or 2), then 2168 Section 16.1 is modified as follows. Recall from Section 9 that a 2169 router can use any routable neighbor as a next hop to a destination, 2170 whether or not the neighbor is advertised in the router-LSA. This is 2171 accomplished by modifying Step 2 so that the router-LSA associated 2172 with the root vertex is replaced with a dummy router-LSA that 2173 includes links to all Full neighbors and all routable MANET 2174 neighbors. In addition, Step 2b (checking for a link from W back to 2175 V) MUST be skipped when V is the root vertex and W is a routable 2176 MANET neighbor. However, Step 2b must still be executed when V is 2177 not the root vertex, to ensure compatibility with OSPFv3. 2179 If LSAFullness is 0 (minimal LSAs), then the calculated paths need 2180 not be shortest paths. In this case, the path actually taken by a 2181 packet can be shorter than the calculated path, since intermediate 2182 routers may have routable neighbors that are not advertised in any 2183 router-LSA. 2185 If full-topology adjacencies and partial-topology LSAs are used, then 2186 Section 16.1 is modified as follows. Step 2 is modified so that the 2187 router-LSA associated with the root vertex is replaced with a dummy 2188 router-LSA that includes links to all Full neighbors. In addition, 2189 Step 2b MUST be skipped when V is the root vertex and W is a Full 2190 MANET neighbor. (This is necessary since the neighbor's router-LSA 2191 need not contain a link back to the router.) 2193 If adjacency reduction is used with partial-topology LSAs, then the 2194 set of routable neighbors can change without causing the contents of 2195 the router-LSA to change. This could happen, for example, if a 2196 routable neighbor that was not included in the router-LSA transitions 2197 to the Down or Init state. Therefore, if the set of routable 2198 neighbors changes, the shortest-path tree must be recalculated even 2199 if the router-LSA does not change. 2201 After the shortest-path tree and routing table are calculated, the 2202 set of routable neighbors must be updated, since a route to a non- 2203 routable neighbor may have been discovered. If the set of routable 2204 neighbors changes, then the shortest-path tree and routing table must 2205 be calculated a second time. The second calculation will not change 2206 the set of routable neighbors again, so two calculations are 2207 sufficient. If the set of routable neighbors is updated periodically 2208 every HelloInterval seconds, then it is not necessary to update the 2209 set of routable neighbors immediately after the routing table is 2210 updated. 2212 11. Security Considerations 2214 As with OSPFv3 [RFC5340], OSPF-MDR can use the IPv6 Authentication 2215 Header (AH) [RFC4302] and/or the IPv6 Encapsulation Security Payload 2216 (ESP) [RFC4303] to provide authentication, integrity, and/or 2217 confidentiality. The use of AH and ESP for OSPFv3 is described in 2218 [RFC4552]. 2220 Generic threats to routing protocols are described and categorized in 2221 [RFC4593]. The mechanisms described in [RFC4552] provide protection 2222 against many of these threats, but not all of them. In particular, 2223 as mentioned in [RFC5340], these mechanisms do not provide protection 2224 against compromised, malfunctioning, or misconfigured routers (also 2225 called Byzantine routers); this is true for both OSPFv3 and OSPF-MDR. 2227 The extension of OSPFv3 to include MANET routers does not introduce 2228 any new security threats. However, the use of a wireless medium and 2229 lack of infrastructure, inherent with MANET routers, may render some 2230 of the attacks described in [RFC4593] easier to mount. Depending on 2231 the network context, these increased vulnerabilities may increase the 2232 need to provide authentication, integrity, and/or confidentiality, as 2233 well as anti-replay service. 2235 For example, sniffing of routing information and traffic analysis are 2236 easier tasks with wireless routers than with wired routers, since the 2237 attacker only needs to be within the radio range of a router. The 2238 use of confidentiality (encryption) provides protection against 2239 sniffing but not traffic analysis. 2241 Similarly, interference attacks are also easier to mount against 2242 MANET routers due to their wireless nature. Such attacks can be 2243 mounted even if OSPF packets are protected by authentication and 2244 confidentiality, e.g., by transmitting noise or replaying out-dated 2245 OSPF packets. As discussed below, an anti-replay service (provided 2246 by both ESP and AH) can be used to protect against the latter attack. 2248 The following threat actions are also easier with MANET routers: 2249 spoofing (assuming the identify of a legitimate router), 2250 falsification (sending false routing information), and overloading 2251 (sending or triggering an excessive amount of routing updates). 2252 These attacks are only possible if authentication is not used, or the 2253 attacker takes control of a router or is able to forge legitimacy 2254 (e.g., by discovering the cryptographic key). 2256 [RFC4552] mandates the use of manual keying when current IPsec 2257 protocols are used with OSPFv3. Routers are required to use manually 2258 configured keys with the same security association (SA) parameters 2259 for both inbound and outbound traffic. For MANET routers, this 2260 implies that all routers attached to the same MANET must use the same 2261 key for multicasting packets. This is required in order to achieve 2262 scalability and feasibility, as explained in [RFC4552]. Future 2263 specifications can explore the use of automated key mangement 2264 protocols that may be suitable for MANETs. 2266 As discussed in [RFC4552], the use of manual keys can increase 2267 vulnerability. For example, manual keys are usually long lived, thus 2268 giving an attacker more time to discover the keys. In addition, the 2269 use of the same key on all routers attached to the same MANET leaves 2270 all routers insecure against impersonation attacks if any one of the 2271 routers is compromised. 2273 Although [RFC4302] and [RFC4303] state that implementations of AH and 2274 ESP SHOULD NOT provide anti-replay service in conjunction with SAs 2275 that are manually keyed, it is important to note that such service is 2276 allowed if the sequence number counter at the sender is correctly 2277 maintained across local reboots until the key is replaced. 2278 Therefore, it may be possible for MANET routers to make use of the 2279 anti-replay service provided by AH and ESP. 2281 When an OSPF routing domain includes both MANET networks and fixed 2282 networks, the frequency of OSPF updates either due to actual topology 2283 changes or malfeasance could result in instability in the fixed 2284 networks. In situations where this is a concern, it is recommended 2285 that the border routers segregate the MANET networks from the fixed 2286 networks with either separate OSPF areas or, in cases where legacy 2287 routers are very sensitive to OSPF update frequency, separate OSPF 2288 instances. With separate OSPF areas, the 5 second MinLSInterval will 2289 dampen the frequency of changes originated in the MANET networks. 2290 Additionally, OSPF ranges can be configured to aggregate prefixes for 2291 the areas supporting MANET networks. With separate OSPF instances, 2292 more conservative local policies can be employed to limit the volume 2293 of updates emanating from the MANET networks. 2295 12. IANA Considerations 2297 This document defines three new LLS TLV types to be allocated by 2298 IANA: MDR-Hello TLV, MDR-Metric TLV, and MDR-DD TLV (see Section 2299 A.2). 2301 13. Acknowledgments 2303 Thanks to Aniket Desai for helpful discussions and comments, 2304 including the suggestion that Router Priority should come before MDR 2305 Level in the lexicographical comparison of (RtrPri, MDR Level, RID) 2306 when selecting MDRs and BMDRs, and that the MDR calculation should be 2307 repeated if it causes the MDR Level to change. Thanks also to Tom 2308 Henderson, Acee Lindem, and Emmanuel Baccelli for helpful discussions 2309 and comments. 2311 14. Normative References 2313 [LLS] Zinin, A., A. Roy, L. Nguyen, B. Friedman, and D. Yeung, "OSPF 2314 Link-local Signaling", draft-ietf-ospf-lls-06.txt (work in 2315 progress), December 2008. 2317 [RFC2119] Bradner, S., "Key words for use in RFC's to Indicate 2318 Requirement Levels", RFC 2119, March 1997. 2320 [RFC2328] Moy, J., "OSPF Version 2", RFC 2328, April 1998. 2322 [RFC4302] Kent, S., "IP Authentication Header", RFC 4302, December 2323 2005. 2325 [RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)", RFC 2326 4303, December 2005. 2328 [RFC4552] Gupta, M. and N. Melam, "Authentication/Confidentiality for 2329 OSPFv3", RFC 4552, June 2006. 2331 [RFC5243] Ogier, R., "OSPF Database Exchange Summary List 2332 Optimization", RFC 5243, May 2008. 2334 [RFC5340] Coltun, R., D. Ferguson, J. Moy, and A. Lindem, "OSPF for 2335 IPv6", RFC 5340, July 2008. 2337 15. Informative References 2339 [Lawler] Lawler, E., "Combinatorial Optimization: Networks and 2340 Matroids", Holt, Rinehart, and Winston, New York, 1976. 2342 [Suurballe] Suurballe, J.W. and R.E. Tarjan, "A Quick Method for 2343 Finding Shortest Pairs of Disjoint Paths", Networks, Vol. 14, 2344 pp. 325-336, 1984. 2346 [RFC4593] Barbir, A., Murphy, S., and Y. Yang, "Generic Threats to 2347 Routing Protocols", RFC 4593, October 2006. 2349 A. Packet Formats 2351 A.1. Options Field 2353 The L bit of the OSPF options field is used for link-local signaling, 2354 as described in [LLS]. Routers set the L bit in Hello and DD packets 2355 to indicate that the packet contains an LLS data block. Routers set 2356 the L bit in a self-originated router-LSA to indicate that the LSA is 2357 non-ackable. 2359 A.2. Link-Local Signaling 2361 OSPF-MDR uses link-local signaling [LLS] to append the MDR-Hello TLV 2362 and MDR-Metric TLV to Hello packets, and to append the MDR-DD TLV to 2363 Database Description packets. Link-local signaling is an extension 2364 of OSPFv2 and OSPFv3 that allows the exchange of arbitrary data using 2365 existing OSPF packet types. Here we use LLS for OSPFv3, which is 2366 accomplished by adding an LLS data block at the end of the OSPFv3 2367 packet. The OSPF packet length field does not include the length of 2368 the LLS data block, but the IPv6 packet length does include this 2369 length. 2371 A.2.1 LLS Data Block 2373 The data block used for link-local signaling is formatted as 2374 described below in Figure A.1. 2376 0 1 2 3 2377 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 2378 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2379 | Checksum | LLS Data Length | 2380 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2381 | | 2382 | LLS TLVs | 2383 . . 2384 . . 2385 . . 2386 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2387 Figure A.1: Format of LLS Data Block 2389 The Checksum field contains the standard IP checksum of the entire 2390 contents of the LLS block. 2392 The 16-bit LLS Data Length field contains the length (in 32-bit 2393 words) of the LLS block including the header and payload. 2394 Implementations should not use the Length field in the IPv6 packet 2395 header to determine the length of the LLS data block. 2397 The rest of the block contains a set of Type/Length/Value (TLV) 2398 triplets as described in the following section. All TLVs must be 2399 32-bit aligned (with padding if necessary). 2401 A.2.2 LLS TLV Format 2403 The contents of LLS data block is constructed using TLVs. See Figure 2404 A.2 for the TLV format. 2406 The type field contains the TLV ID which is unique for each type of 2407 TLV. The Length field contains the length of the Value field (in 2408 bytes) that is variable and contains arbitrary data. 2410 0 1 2 3 2411 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 2412 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2413 | Type | Length | 2414 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2415 | | 2416 . . 2417 . Value . 2418 . . 2419 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2420 Figure A.2: Format of LLS TLVs 2422 Note that TLVs are always padded to 32-bit boundary, but padding 2423 bytes are not included in TLV Length field (though it is included in 2424 the LLS Data Length field of the LLS block header). All unknown TLVs 2425 MUST be silently ignored. 2427 A.2.3 MDR-Hello TLV 2429 The MDR-Hello TLV is appended to each MANET Hello using LLS. It 2430 includes the current Hello sequence number (HSN) for the transmitting 2431 interface and the number of neighbors of each type that are listed in 2432 the body of the Hello (see Section 4.1). It also indicates whether 2433 the Hello is differential (via the D-bit), and whether the router is 2434 using full-topology adjacencies (via the A-bit). 2436 0 1 2 3 2437 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 2438 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2439 | Type | Length | 2440 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2441 | Hello Sequence Number | Reserved |A|D| 2442 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2443 | N1 | N2 | N3 | N4 | 2444 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2446 o Type: Set to 14. 2447 o Length: Set to 8. 2448 o Hello Sequence Number: A circular two octet unsigned integer 2449 indicating the current HSN for the transmitting interface. The 2450 HSN for the interface is incremented by 1 (modulo 2^16) every 2451 time a (differential or full) Hello is sent on the interface. 2452 o Reserved: Set to 0. Reserved for future use. 2453 o A (1 bit): Set to 1 if AdjConnectivity is 0, otherwise set to 0. 2454 o D (1 bit): Set to 1 for a differential Hello and 0 for a full 2455 Hello. 2456 o N1 (8 bits): The number of neighbors listed in the Hello that 2457 are in state Down. N1 is zero if the the Hello is not 2458 differential. 2459 o N2 (8 bits): The number of neighbors listed in the Hello that 2460 are in state Init. 2462 o N3 (8 bits): The number of neighbors listed in the Hello that 2463 are Dependent. 2464 o N4 (8 bits): The number of neighbors listed in the Hello that 2465 are Selected Advertised Neighbors. 2467 A.2.4 MDR-DD TLV 2469 When a Database Description packet is sent to a neighbor in state 2470 ExStart, an MDR-DD TLV is appended to the packet using LLS. It 2471 includes the same two Router IDs that are included in the DR and 2472 Backup DR fields of a Hello sent by the router, and is used to 2473 indicate the router's MDR Level and Parent(s). 2475 0 1 2 3 2476 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 2477 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2478 | Type | Length | 2479 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2480 | DR | 2481 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2482 | Backup DR | 2483 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ 2485 o Type: Set to 15. 2486 o Length: Set to 8. 2487 o DR: The same Router ID that is included in the DR field of a 2488 Hello sent by the router (see Section A.3). 2489 o Backup DR: The same Router ID that is included in the Backup DR 2490 field of a Hello sent by the router (see Section A.3). 2492 A.2.5 MDR-Metric TLV 2494 If LSAFullness is 1 or 2, an MDR-Metric TLV must be appended to each 2495 MANET Hello packet using LLS, unless all link metrics are 1. This 2496 TLV advertises the link metric for each bidirectional neighbor listed 2497 in the body of the Hello. At a minimum, this TLV advertises a single 2498 default metric. If the I bit is set, the Router ID and link metric 2499 are included for each bidirectional neighbor listed in the body of 2500 the Hello whose link metric is not equal to the default metric. This 2501 option reduces overhead when all neighbors have the same link metric, 2502 or only a few neighbors have a link metric that differs from the 2503 default metric. If the I bit is zero, the link metric is included 2504 for each bidirectional neighbor that is listed in the body of the 2505 Hello and the neighbor RIDs are omitted from the TLV. 2507 0 1 2 3 2508 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 2509 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2510 | Type | Length | 2511 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2512 | Default Metric | Reserved |I| 2513 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2514 | Neighbor ID (1) | 2515 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2516 | Neighbor ID (2) | 2517 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2518 | ... | 2519 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2520 | Metric (1) | Metric (2) | 2521 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2522 | ... 2523 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2525 o Type: Set to 16. 2526 o Length: Set to 4 + 6*N if the I bit is 1, and to 4 + 2*N if the I 2527 bit is 0, where N is the number of neighbors included in the TLV. 2528 o Default Metric: If the I bit is 1, this is the link metric that 2529 applies to every bidirectional neighbor listed in the body of 2530 the Hello whose RID is not listed in the Metric TLV. 2531 o Neighbor ID: If the I bit is 1, the RID is listed for each 2532 bidirectional neighbor (Lists 3 through 5 as defined in 2533 Section 4.1) in the body of the Hello whose link metric is not 2534 equal to the default metric. Omitted if the I bit is 0. 2535 o Metric: Link metric for each bidirectional neighbor, listed in 2536 the same order as the Neighbor IDs in the TLV if the I bit is 1, 2537 and in the same order as the Neighbor IDs of bidirectional 2538 neighbors (Lists 3 through 5 as defined in Section 4.1) 2539 in the body of the Hello if the I bit is 0. 2541 A.3. Hello Packet DR and Backup DR Fields 2543 The Designated Router (DR) and Backup DR fields of a Hello packet are 2544 set as follows: 2546 o DR: This field is the router's Parent, or is 0.0.0.0 if the 2547 Parent is null. The Parent of an MDR is always the router's 2548 own RID. 2550 o Backup DR: This field is the router's Backup Parent, or is 2551 0.0.0.0 if the Backup Parent is null. The Backup Parent of a 2552 BMDR is always the router's own RID. 2554 A.4. LSA Formats and Examples 2556 LSA formats are specified in [RFC5340] Section 4.4. Figure A.3 below 2557 gives an example network map for a MANET in a single area. 2559 o Four MANET routers RT1, RT2, RT3, and RT4 are in area 1. 2560 o RT1's MANET interface has links to RT2 and RT3's MANET interfaces. 2561 o RT2's MANET interface has links to RT1 and RT3's MANET interfaces. 2562 o RT3's MANET interface has links to RT1, RT2, and RT3's MANET 2563 interfaces. 2564 o RT4's MANET interface has a link to RT3's MANET interface. 2565 o RT1 and RT2 have stub networks attached on broadcast interfaces. 2566 o RT3 has a transit network attached on a broadcast interface. 2568 .......................................... 2569 . Area 1. 2570 . + . 2571 . | . 2572 . | 2+---+1 1+---+ 2573 . N1 |---|RT1|----+ +---|RT4|---- 2574 . | +---+ |\ / +---+ 2575 . | | \ / . 2576 . + | \ N3 / . 2577 . | \ / . 2578 . + | \ / . 2579 . | | \ / . 2580 . | 2+---+1 | \ / . 2581 . N2 |---|RT2|----+-------+ . 2582 . | +---+ |1 . 2583 . | +---+ . 2584 . | |RT3|---------------- 2585 . + +---+ . 2586 . |2 . 2587 . +------------+ . 2588 . |1 N4 . 2589 . +---+ . 2590 . |RT5| . 2591 . +---+ . 2592 .......................................... 2594 Figure A.3: Area 1 with IP addresses shown 2595 Network IPv6 prefix 2596 ----------------------------------- 2597 N1 5f00:0000:c001:0200::/56 2598 N2 5f00:0000:c001:0300::/56 2599 N4 5f00:0000:c001:0400::/56 2601 Table 1: IPv6 link prefixes for sample network 2603 Router interface Interface ID IPv6 global unicast prefix 2604 ----------------------------------------------------------- 2605 RT1 LOOPBACK 0 5f00:0001::/64 2606 to N3 1 n/a 2607 to N1 2 5f00:0000:c001:0200::RT1/56 2608 RT2 LOOPBACK 0 5f00:0002::/64 2609 to N3 1 n/a 2610 to N2 2 5f00:0000:c001:0300::RT2/56 2611 RT3 LOOPBACK 0 5f00:0003::/64 2612 to N3 1 n/a 2613 to N4 2 5f00:0000:c001:0400::RT3/56 2614 RT4 LOOPBACK 0 5f00:0004::/64 2615 to N3 1 n/a 2616 RT5 to N4 1 5f00:0000:c001:0400::RT5/56 2618 Table 2: IPv6 link prefixes for sample network 2620 Router interface Interface ID link-local address 2621 ------------------------------------------------------- 2622 RT1 LOOPBACK 0 n/a 2623 to N1 1 fe80:0001::RT1 2624 to N3 2 fe80:0002::RT1 2625 RT2 LOOPBACK 0 n/a 2626 to N2 1 fe80:0001::RT2 2627 to N3 2 fe80:0002::RT2 2628 RT3 LOOPBACK 0 n/a 2629 to N3 1 fe80:0001::RT3 2630 to N4 2 fe80:0002::RT3 2631 RT4 LOOPBACK 0 n/a 2632 to N3 1 fe80:0001::RT4 2633 RT5 to N4 1 fe80:0002::RT5 2635 Table 3: OSPF Interface IDs and link-local addresses 2637 A.4.1 Router-LSAs 2639 As an example, consider the router-LSA that node RT3 would originate. 2640 The node consists of one MANET, one broadcast, and one loopback 2641 interface. 2643 RT3's router-LSA 2645 LS age = DoNotAge+0 ;newly originated 2646 LS type = 0x2001 ;router-LSA 2647 Link State ID = 0 ;first fragment 2648 Advertising Router = 192.1.1.3 ;RT3's Router ID 2649 bit E = 0 ;not an AS boundary router 2650 bit B = 1 ;area border router 2651 Options = (V6-bit|E-bit|R-bit) 2652 Type = 1 ;p2p link to RT1 2653 Metric = 1 ;cost to RT1 2654 Interface ID = 1 ;Interface ID 2655 Neighbor Interface ID = 1 ;Interface ID 2656 Neighbor Router ID = 192.1.1.1 ;RT1's Router ID 2657 Type = 1 ;p2p link to RT2 2658 Metric = 1 ;cost to RT2 2659 Interface ID = 1 ;Interface ID 2660 Neighbor Interface ID = 1 ;Interface ID 2661 Neighbor Router ID = 192.1.1.2 ;RT2's Router ID 2662 Type = 1 ;p2p link to RT4 2663 Metric = 1 ;cost to RT4 2664 Interface ID = 1 ;Interface ID 2665 Neighbor Interface ID = 1 ;Interface ID 2666 Neighbor Router ID = 192.1.1.4 ;RT4's Router ID 2667 Type = 2 ;connects to N4 2668 Metric = 1 ;cost to N4 2669 Interface ID = 2 ;RT3's Interface ID 2670 Neighbor Interface ID = 1 ;RT5's Interface ID (elected DR) 2671 Neighbor Router ID = 192.1.1.5 ;RT5's Router ID (elected DR) 2673 A.4.2 Link-LSAs 2675 Consider the link-LSA that RT3 would originate for its MANET 2676 interface. 2678 RT3's Link-LSA for its MANET interface 2680 LS age = DoNotAge+0 ;newly originated 2681 LS type = 0x0008 ;Link-LSA 2682 Link State ID = 1 ;Interface ID 2683 Advertising Router = 192.1.1.3 ;RT3's Router ID 2684 RtrPri = 1 ;default priority 2685 Options = (V6-bit|E-bit|R-bit) 2686 Link-local Interface Address = fe80:0001::RT3 2687 # prefixes = 0 ;no global unicast address 2689 A.4.3 Intra-Area-Prefix-LSAs 2691 A MANET node originates an intra-area-prefix-LSA to advertise its own 2692 prefixes, and those of its attached networks or stub links. As an 2693 example, consider the intra-area-prefix-LSA that RT3 will build. 2695 RT2's intra-area-prefix-LSA for its own prefixes 2697 LS age = DoNotAge+0 ;newly originated 2698 LS type = 0x2009 ;intra-area-prefix-LSA 2699 Link State ID = 177 ;or something 2700 Advertising Router = 192.1.1.3 ;RT3's Router ID 2701 # prefixes = 2 2702 Referenced LS type = 0x2001 ;router-LSA reference 2703 Referenced Link State ID = 0 ;always 0 for router-LSA reference 2704 Referenced Advertising Router = 192.1.1.3 ;RT2's Router ID 2705 PrefixLength = 64 ;prefix on RT3's LOOPBACK 2706 PrefixOptions = 0 2707 Metric = 0 ;cost of RT3's LOOPBACK 2708 Address Prefix = 5f00:0003::/64 2709 PrefixLength = 56 ;prefix on RT3's interface 2 2710 PrefixOptions = 0 2711 Metric = 1 ;cost of RT3's interface 2 2712 Address Prefix = 5f00:0000:c001:0400::RT3/56 ;pad 2714 B. Detailed Algorithms for MDR/BMDR Selection 2716 This section provides detailed algorithms for Step 2.4 of Phase 2 2717 (MDR Selection) and Step 3.2 of Phase 3 (BMDR Selection) of the MDR 2718 selection algorithm described in Section 5. Step 2.4 uses a breadth- 2719 first search (BFS) algorithm, and Step 3.2 uses an efficient 2720 algorithm for finding pairs of node-disjoint paths from Rmax to all 2721 other neighbors. Both algorithms run in O(d^2) time, where d is the 2722 number of neighbors. 2724 For convenience, in the following description, the term "bi-neighbor" 2725 will be used as an abbreviation for "bidirectional neighbor". Also, 2726 node i denotes the router performing the calculation. 2728 B.1. Detailed Algorithm for Step 2.4 (MDR Selection) 2730 The following algorithm performs Step 2.4 of the MDR selection 2731 algorithm, and assumes that Phase 1 and Steps 2.1 through 2.3 have 2732 been performed, so that the neighbor connectivity matrix NCM has been 2733 computed, and Rmax is the bi-neighbor with the (lexicographically) 2734 largest value of (RtrPri, MDR Level, RID). The BFS algorithm uses a 2735 FIFO queue so that all nodes 1 hop from node Rmax are processed 2736 first, then 2 hops, etc. When the BFS algorithm terminates, hops(u), 2737 for each bi-neighbor node u of node i, will be equal to the minimum 2738 number of hops from node Rmax to node u, using only intermediate 2739 nodes that are bi-neighbors of node i and that have a larger value of 2740 (RtrPri, MDR Level, RID) than node i. The algorithm also computes, 2741 for each node u, the tree parent p(u) and the second node r(u) on the 2742 tree path from Rmax to u, which will be used in Step 3.2. 2744 (a) Compute a matrix of link costs c(u,v) for each pair of 2745 bi-neighbors u and v as follows: If node u has a larger value 2746 of (RtrPri, MDR Level, RID) than node i, and NCM(u,v) = 1, 2747 then set c(u,v) to 1. Otherwise, set c(u,v) to infinity. 2748 (Note that the matrix NCM(u,v) is symmetric, but the matrix 2749 c(u,v) is not.) 2751 (b) Set hops(u) = infinity for all bi-neighbors u other than Rmax, 2752 and set hops(Rmax) = 0. Initially, p(u) is undefined for each 2753 neighbor u. For each bi-neighbor u such that c(Rmax,u) = 1, 2754 set r(u) = u; for all other u, r(u) is initially undefined. 2755 Add node Rmax to the FIFO queue. 2757 (c) While the FIFO queue is nonempty: 2758 Remove the node at the head of the queue; call it node u. 2759 For each bi-neighbor v of node i such that c(u,v) = 1: 2760 If hops(v) > hops(u) + 1, then set hops(v) = hops(u) + 1, 2761 set p(v) = u, set r(v) = r(u) if hops(v) > 1, and add 2762 node v to the tail of the queue. 2764 B.2. Detailed Algorithm for Step 3.2 (BMDR Selection) 2766 Step 3.2 of the MDR selection algorithm requires the router to 2767 determine whether there exist two node-disjoint paths from Rmax to 2768 each other bi-neighbor u, via bi-neighbors that have a larger value 2769 of (RtrPri, MDR Level, RID) than the router itself. This information 2770 is needed to determine whether the router should select itself as a 2771 BMDR. 2773 It is possible to determine separately for each bi-neighbor u whether 2774 there exist two node-disjoint paths from Rmax to u, using the well- 2775 known augmenting path algorithm [Lawler] which runs in O(n^2) time, 2776 but this must be done for all bi-neighbors u, thus requiring a total 2777 run time of O(n^3). The algorithm described below makes the same 2778 determination simultaneously for all bi-neighbors u, achieving a much 2779 faster total run time of O(n^2). The algorithm is a simplified 2780 variation of the Suurballe-Tarjan algorithm [Suurballe] for finding 2781 pairs of disjoint paths. 2783 The algorithm described below uses the following output of Phase 2: 2784 the tree parent p(u) of each node (which defines the BFS tree 2785 computed in Phase 2), and the second node r(u) on the tree path from 2786 Rmax to u. 2788 The algorithm uses the following concepts. For any node u on the BFS 2789 tree other than Rmax, we define g(u) to be the first labeled node on 2790 the reverse tree path from u to Rmax, if such a labeled node exists 2791 other than Rmax. (The reverse tree path consists of u, p(u), 2792 p(p(u)), ..., Rmax.) If no such labeled node exists, then g(u) is 2793 defined to be r(u). In particular, if u is labeled then g(u) = u. 2794 Note that g(u) either must be labeled or must be a neighbor of Rmax. 2796 For any node k that either is labeled or is a neighbor of Rmax, we 2797 define the unlabeled subtree rooted at k, denoted S(k), to be the set 2798 of nodes u such that g(u) = k. Thus, S(k) includes node k itself and 2799 the set of unlabeled nodes downstream of k on the BFS tree that can 2800 be reached without going through any labeled nodes. This set can be 2801 obtained in linear time using a depth-first search starting at node 2802 k, and using labeled nodes to indicate the boundaries of the search. 2803 Note that g(u) and S(k) are not maintained as variables in the 2804 algorithm given below, but simply refer to the definitions given 2805 above. 2807 The BMDR algorithm maintains a set B, which is initially empty. A 2808 node u is added to B when it is known that two node-disjoint paths 2809 exist from Rmax to u via nodes that have a larger value of (RtrPri, 2810 MDR Level, RID) than the router itself. When the algorithm 2811 terminates, B consists of all nodes that have this property. 2813 The algorithm consists of the following two steps. 2815 (a) Mark Rmax as labeled. For each pair of nodes u, v on the BFS 2816 tree other than Rmax such that r(u) is not equal to r(v) (i.e., 2817 u and v have different second nodes), NCM(u,v) = 1, and node u 2818 has a greater value of (RtrPri, MDR level, RID) than the router 2819 itself, add v to B. (Clearly there are two disjoint paths from 2820 Rmax to v.) 2822 (b) While there exists a node in B that is not labeled, do the 2823 following. Choose any node k in B that is not labeled, and let 2824 j = g(k). Now mark k as labeled. (This creates a new unlabeled 2825 subtree S(k), and makes S(j) smaller by removing S(k) from it.) 2826 For each pair of nodes u, v such that u is in S(k), v is in 2827 S(j), and NCM(u,v) = 1: 2829 o If u has a larger value of (RtrPri, MDR level, RID) than the 2830 router itself, and v is not in B, then add v to B. 2832 o If v has a larger value of (RtrPri, MDR level, RID) than the 2833 router itself, and u is not in B, then add u to B. 2835 A simplified version of the algorithm MAY be performed by omitting 2836 step (b). However, the simplified algorithm will result in more 2837 BMDRs, and is not recommended if AdjConnectivity = 2 since it will 2838 result in more adjacencies. 2840 The above algorithm can be executed in O(n^2) time, where n is the 2841 number of neighbors. Step (a) clearly requires O(n^2) time since it 2842 considers all pairs of nodes u and v. Step (b) also requires O(n^2) 2843 time because each pair of nodes is considered at most once. This is 2844 because labeling nodes divides unlabeled subtrees into smaller 2845 unlabeled subtrees, and a given pair u, v is considered only the 2846 first time u and v belong to different unlabeled subtrees. 2848 C. Min-Cost LSA Algorithm 2850 This section describes the algorithm for determining which MANET 2851 neighbors to include in the router-LSA when LSAFullness is 1. The 2852 min-cost LSA algorithm ensures that the link-state database provides 2853 sufficient information to calculate at least one shortest (minimum- 2854 cost) path to each destination. The algorithm assumes that a router 2855 may have multiple interfaces, at least one of which is a MANET 2856 interface. The algorithm becomes significantly simpler if the router 2857 has only a single (MANET) interface. 2859 The input to this algorithm includes information obtained from Hellos 2860 received from each neighbor on each MANET interface, including the 2861 neighbor's Bidirectional Neighbor Set (BNS), Dependent Neighbor Set 2862 (DNS), Selected Advertised Neighbor Set (SANS), and link metrics. 2863 The input also includes the link-state database if the router has a 2864 non-MANET interface. 2866 The output of the algorithm is the router's SANS for each MANET 2867 interface. The SANS is used to construct the router-LSA as described 2868 in Section 9.4. The min-cost LSA algorithm must be run to update the 2869 SANS (and possibly originate a new router-LSA) either periodically 2870 just before sending each Hello, or whenever any of the following 2871 events occurs: 2873 o The state or routability of a neighbor changes. 2874 o A Hello received from a neighbor indicates a change in its 2875 MDR Level, Router Priority, FullHelloRcvd, BNS, DNS, SANS, 2876 Parent(s), or link metrics. 2877 o An LSA originated by a non-MANET neighbor is received. 2879 Although the algorithm described below runs in O(d^3) time, where d 2880 is the number of neighbors, an incremental version for a single 2881 topology change runs in O(d^2) time, as discussed following the 2882 algorithm description. 2884 For convenience, in the following description, the term "bi-neighbor" 2885 will be used as an abbreviation for "bidirectional neighbor". Also, 2886 router i will denote the router doing the calculation. To perform 2887 the min-cost LSA algorithm, the following steps are performed. 2889 (1) Create the neighbor connectivity matrix (NCM) for each MANET 2890 interface, as described in Section 5.1. Create the multiple- 2891 interface neighbor connectivity matrix MNCM as follows. For each 2892 bi-neighbor j, set MNCM(i,j) = MNCM(j,i) = 1. For each pair j, k 2893 of MANET bi-neighbors, set MNCM(j,k) = 1 if NCM(j,k) equals 1 for 2894 any MANET interface. For each pair j, k of non-MANET bi- 2895 neighbors, set MNCM(j,k) = 1 if the link-state database indicates 2896 that a direct link exists between j and k. Otherwise, set 2897 MNCM(j,k) = 0. (Note that a given router can be a neighbor on 2898 both a MANET interface and a non-MANET interface.) 2900 (2) Create the inter-neighbor cost matrix (COST) as follows. For 2901 each pair j, k of routers such that each of j and k is a bi- 2902 neighbor or router i itself: 2904 (a) If MNCM(j,k) = 1, set COST(j,k) to the metric of the link 2905 from j to k obtained from j's Hellos (for a MANET interface), 2906 or from the link-state database (for a non-MANET interface). 2907 If there are multiple links from j to k (via multiple 2908 interfaces), COST(j,k) is set to the minimum cost of these 2909 links. 2911 (b) Otherwise, set COST(j,k) to LSInfinity. 2913 (3) Create the backbone neighbor matrix (BNM) as follows. BNM 2914 indicates which pairs of MANET bi-neighbors are backbone 2915 neighbors of each other, as defined in Section 9.2.1. If 2916 adjacency reduction is not used (AdjConnectivity = 0), set all 2917 entries of BNM to zero and proceed to Step 4. 2919 In the following, if a link exists from router j to router k on 2920 more than one interface, we consider only interfaces for which 2921 the cost from j to k equals COST(j,k); such interfaces will be 2922 called "candidate" interfaces. 2924 For each pair j, k of MANET bi-neighbors, BNM(j,k) is set to 1 if 2925 j and k are backbone neighbors of each other on a candidate MANET 2926 interface. That is, BNM(j,k) is set to 1 if, for any candidate 2927 MANET interface, NCM(j,k) = 1 and either of the following 2928 conditions is satisfied: 2930 (a) Router k is included in j's DNS or router j is included in 2931 k's DNS. 2933 (b) Router j is the (Backup) Parent of router k or router k is 2934 the (Backup) Parent of router j. 2936 Otherwise, BNM(j,k) is set to 0. 2938 (4) Create the selected advertised neighbor matrix (SANM) as follows. 2939 For each pair j, k of routers such that each of j and k is a bi- 2940 neighbor or router i itself, SANM(j,k) is set to 1 if, for any 2941 candidate MANET interface, NCM(j,k) = 1 and k is included in j's 2942 SANS. Otherwise, SANM(j,k) is set to 0. Note that SANM(i,k) is 2943 set to 1 if k is currently a selected advertised neighbor. 2945 (5) Compute the new set of selected advertised neighbors as follows. 2946 For each MANET bi-neighbor j, initialize the bit variable 2947 new_sel_adv(j) to 0. (This bit will be set to 1 if j is 2948 selected.) For each MANET bi-neighbor j: 2950 (a) If j is a bi-neighbor on more than one interface, consider 2951 only candidate interfaces (for which the cost to j is 2952 minimum). If one of the candidate interfaces is a non-MANET 2953 interface, examine the next neighbor (j is not selected since 2954 it will be advertised anyway). 2956 (b) If adjacency reduction is used, and one of the candidate 2957 interfaces is a MANET interface on which j is a backbone 2958 neighbor (see Section 9.2), examine the next neighbor (j is 2959 not selected since it will be advertised anyway). 2961 (c) Otherwise, if there is more than one candidate MANET 2962 interface, select the "preferred" interface by using the 2963 following preference rules in the given order: an interface 2964 is preferred if (1) router i's SANS for that interface 2965 already includes j, (2) router i's Router Priority is larger 2966 on that interface, and (3) router i's MDR level is larger on 2967 that interface. 2969 (d) For each bi-neighbor k (on any interface) such that COST(k,j) 2970 > COST(k,i) + COST(i,j), determine whether there exists 2971 another bi-neighbor u such that either COST(k,u) + COST(u,j) 2972 < COST(k,i) + COST(i,j), or COST(k,u) + COST(u,j) = COST(k,i) 2973 + COST(i,j) and either of the following conditions is true: 2975 o BNM(u,j) = 1, or 2976 o (SANM(j,u), SANM(u,j), RtrPri(u), RID(u)) 2977 is lexicographically greater than 2978 (SANM(j,i), SANM(i,j), RtrPri(i), RID(i)). 2980 If for some such bi-neighbor k, there does not exist such a 2981 bi-neighbor u, then set new_sel_adv(j) = 1. 2983 (6) For each MANET interface I, update the SANS to equal the set of 2984 all bi-neighbors j such that new_sel_adv(j) = 1 and I is the 2985 preferred interface for j. 2987 (7) With the SANS updated, a new router-LSA may need to be originated 2988 as described in Section 9.4. 2990 The lexicographical comparison of Step 5d gives preference to links 2991 that are already advertised, in order to improve LSA stability. 2993 The above algorithm can be run in O(d^2) time if a single link change 2994 occurs. For example, if link (x,y) fails where x and y are neighbors 2995 of router i, and either SANS(x,y) = 1 or BNM(x,y) = 1, then Step 5 2996 need only be performed for pairs j, k such that either j or k is 2997 equal to x or y. 2999 D. Non-Ackable LSAs for Periodic Flooding 3001 In a highly mobile network, it is possible that a router almost 3002 always originates a new router-LSA every MinLSInterval seconds. In 3003 this case, it should not be necessary to send Acks for such an LSA, 3004 or to retransmit such an LSA as a unicast, or to describe such an LSA 3005 in a DD packet. In this case, the originator of an LSA MAY indicate 3006 that the router-LSA is "non-ackable" by setting the L bit in the 3007 options field of the LSA (see Section A.1). For example, a router 3008 can originate non-ackable LSAs if it determines (e.g., based on an 3009 exponential moving average) that a new LSA is originated every 3010 MinLSInterval seconds at least 90 percent of the time. (Simulations 3011 can be used to determine the best threshold.) 3013 A non-ackable LSA is never acknowledged, nor is it ever retransmitted 3014 as a unicast or described in a DD packet, thus saving substantial 3015 overhead. However, the originating router must periodically 3016 retransmit the current instance of its router-LSA as a multicast 3017 (until it originates a new LSA, which will usually happen before the 3018 previous instance is retransmitted), and each MDR must periodically 3019 retransmit each non-ackable LSA as a multicast (until it receives a 3020 new instance of the LSA, which will usually happen before the 3021 previous instance is retransmitted). For this option to work, 3022 RxmtInterval must be larger than MinLSInterval so that a new instance 3023 of the LSA is usually received before the previous one is 3024 retransmitted. Note that the reception of a retransmitted 3025 (duplicate) LSA does not result in immediate forwarding of the LSA; 3026 only a new LSA (with a larger sequence number) may be forwarded 3027 immediately, according to the flooding procedure of Section 8. 3029 E. Simulation Results 3031 This section presents simulation results that predict the performance 3032 of OSPF-MDR for up to 160 nodes with min-cost LSAs and up to 200 3033 nodes with minimal LSAs. The results were obtained using the GTNetS 3034 simulator with OSPF-MDR version 1.01, available at 3035 http://hipserver.mct.phantomworks.org/ietf/ospf. 3037 The following scenario parameter values were used: radio range = 200 3038 m and 250 m, grid length = 500 m, wireless alpha = 0.5, (maximum) 3039 velocity = 10 m/s, pause time = 0, packet rate = 10 pkts/s, packet 3040 size = 40 bytes, random seed = 8, start time (for gathering 3041 statistics) = 1800 s. The stop time was 3600 s for up to 80 nodes 3042 and 2700 s for more than 80 nodes. The source and destination are 3043 selected randomly for each generated UDP packet. The simulated MAC 3044 protocol is 802.11b. 3046 Tables 4 and 6 show the results for the default configuration of 3047 OSPF-MDR, except that differential Hellos were used (2HopRefresh = 3) 3048 since they are recommended when the number of neighbors is large. 3049 Tables 5 and 7 show the results for the same configuration except 3050 that minimal LSAs were used instead of min-cost LSAs. The tables 3051 show the results for total OSPF overhead in kb/s, the total number of 3052 OSPF packets per second, the delivery ratio for UDP packets, and the 3053 average number of hops traveled by UDP packets that reach their 3054 destination. 3056 Tables 5 and 7 for minimal LSAs also show the following statistics: 3057 the average number of bidirectional neighbors per node, the average 3058 number of fully adjacent neighbors per node, the number of changes in 3059 the set of bidirectional neighbors per node per second, and the 3060 number of changes in the set of fully adjacent neighbors per node per 3061 second. These statistics do not change significantly when min-cost 3062 LSAs are used instead of minimal LSAs. 3064 The results show that OSPF-MDR achieves good performance for up to at 3065 least 160 nodes when min-cost LSAs are used, and up to at least 200 3066 nodes when minimal LSAs are used. Also, the results for the number 3067 of hops show that the routes obtained with minimal LSAs are only 2.3% 3068 to 4.5% longer than with min-cost LSAs when the range is 250 m, and 3069 3.5% to 7.4% longer when the range is 200 m. 3071 The results also show that the number of adjacencies per node and the 3072 number of adjacency changes per node per second do not increase as 3073 the number of nodes increases, and are dramatically smaller than the 3074 number of neighbors per node and the number of neighbor changes per 3075 node per second, respectively. These factors contribute to the low 3076 overhead achieved by OSPF-MDR. For example, the results in Table 5 3077 imply that with 200 nodes and range 250 m, there are 2.136/.039 = 55 3078 times as many adjacency formations with full-topology adjacencies as 3079 with uniconnected adjacencies. Additional simulation results for 3080 OSPF-MDR can be found at http://www.manet-routing.org. 3082 Number of nodes 3083 20 40 60 80 100 120 160 3084 ------------------------------------------------------------------ 3085 OSPF kb/s 27.1 74.2 175.3 248.6 354.6 479.2 795.7 3086 OSPF pkts/s 29.9 69.2 122.9 163.7 210.3 257.2 357.7 3087 Delivery ratio .970 .968 .954 .958 .957 .956 .953 3088 Avg no. hops 1.433 1.348 1.389 1.368 1.411 1.361 1.386 3090 Table 4: Results for range 250 m with min-cost LSAs 3091 Number of nodes 3092 20 40 60 80 120 160 200 3093 ------------------------------------------------------------------ 3094 OSPF kb/s 15.5 41.6 91.0 132.9 246.3 419.0 637.4 3095 OSPF pkts/sec 18.8 42.5 78.6 102.8 166.8 245.6 321.0 3096 Delivery ratio .968 .968 .951 .953 .962 .956 .951 3097 Avg no. hops 1.466 1.387 1.433 1.412 1.407 1.430 1.411 3098 Avg no. nbrs/node 11.38 25.82 36.30 50.13 75.87 98.65 125.59 3099 Avg no. adjs/node 2.60 2.32 2.38 2.26 2.25 2.32 2.13 3100 Nbr changes/node/s .173 .372 .575 .752 1.223 1.654 2.136 3101 Adj changes/node/s .035 .036 .046 .040 .032 .035 .039 3103 Table 5: Results for range 250 m with minimal LSAs 3105 Number of nodes 3106 20 40 60 80 100 120 160 3107 ------------------------------------------------------------------ 3108 OSPF kb/s 40.5 123.4 286.5 415.7 597.5 788.9 1309.8 3109 OSPF pkts/s 37.6 83.9 135.1 168.6 205.4 247.7 352.3 3110 Delivery ratio .926 .919 .897 .900 .898 .895 .892 3111 Avg no. hops 1.790 1.628 1.666 1.632 1.683 1.608 1.641 3113 Table 6: Results for range 200 m with min-cost LSAs 3115 Number of nodes 3116 20 40 60 80 120 160 200 3117 ------------------------------------------------------------------ 3118 OSPF kb/s 24.0 63.6 140.6 195.2 346.9 573.2 824.6 3119 OSPF pkts/sec 26.4 58.8 108.3 138.8 215.2 311.3 401.3 3120 Delivery ratio .930 .927 .897 .907 .907 .904 .902 3121 Avg no. hops 1.853 1.714 1.771 1.743 1.727 1.758 1.747 3122 Avg no. nbrs/node 7.64 18.12 25.27 35.29 52.99 68.13 86.74 3123 Avg no. adjs/node 2.78 2.60 2.70 2.50 2.39 2.36 2.24 3124 Nbr changes/node/s .199 .482 .702 .959 1.525 2.017 2.611 3125 Adj changes/node/s .068 .069 .081 .068 .055 .058 .057 3127 Table 7: Results for range 200 m with minimal LSAs 3129 Authors' Addresses 3131 Richard G. Ogier 3132 SRI International 3133 Email: rich.ogier@earthlink.net 3135 Phil Spagnolo 3136 Boeing Phantom Works 3137 Email: phillipspagnolo@gmail.com