idnits 2.17.1 draft-ietf-lsr-dynamic-flooding-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (May 17, 2020) is 1412 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. 'ISO10589' == Outdated reference: A later version (-09) exists of draft-cc-lsr-flooding-reduction-08 Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force T. Li, Ed. 3 Internet-Draft Arista Networks 4 Intended status: Standards Track P. Psenak, Ed. 5 Expires: November 18, 2020 L. Ginsberg 6 Cisco Systems, Inc. 7 H. Chen 8 Futurewei 9 T. Przygienda 10 Juniper Networks, Inc. 11 D. Cooper 12 CenturyLink 13 L. Jalil 14 Verizon 15 S. Dontula 16 ATT 17 May 17, 2020 19 Dynamic Flooding on Dense Graphs 20 draft-ietf-lsr-dynamic-flooding-05 22 Abstract 24 Routing with link state protocols in dense network topologies can 25 result in sub-optimal convergence times due to the overhead 26 associated with flooding. This can be addressed by decreasing the 27 flooding topology so that it is less dense. 29 This document discusses the problem in some depth and an 30 architectural solution. Specific protocol changes for IS-IS, OSPFv2, 31 and OSPFv3 are described in this document. 33 Status of This Memo 35 This Internet-Draft is submitted in full conformance with the 36 provisions of BCP 78 and BCP 79. 38 Internet-Drafts are working documents of the Internet Engineering 39 Task Force (IETF). Note that other groups may also distribute 40 working documents as Internet-Drafts. The list of current Internet- 41 Drafts is at https://datatracker.ietf.org/drafts/current/. 43 Internet-Drafts are draft documents valid for a maximum of six months 44 and may be updated, replaced, or obsoleted by other documents at any 45 time. It is inappropriate to use Internet-Drafts as reference 46 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on November 18, 2020. 50 Copyright Notice 52 Copyright (c) 2020 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (https://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with respect 60 to this document. Code Components extracted from this document must 61 include Simplified BSD License text as described in Section 4.e of 62 the Trust Legal Provisions and are provided without warranty as 63 described in the Simplified BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 68 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 5 69 2. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 5 70 3. Solution Requirements . . . . . . . . . . . . . . . . . . . . 5 71 4. Dynamic Flooding . . . . . . . . . . . . . . . . . . . . . . 6 72 4.1. Applicability . . . . . . . . . . . . . . . . . . . . . . 7 73 4.2. Leader election . . . . . . . . . . . . . . . . . . . . . 8 74 4.3. Computing the Flooding Topology . . . . . . . . . . . . . 8 75 4.4. Topologies on Complete Bipartite Graphs . . . . . . . . . 9 76 4.4.1. A Minimal Flooding Topology . . . . . . . . . . . . . 9 77 4.4.2. Xia Topologies . . . . . . . . . . . . . . . . . . . 10 78 4.4.3. Optimization . . . . . . . . . . . . . . . . . . . . 11 79 4.5. Encoding the Flooding Topology . . . . . . . . . . . . . 11 80 4.6. Advertising the Local Edges Enabled for Flooding . . . . 11 81 5. Protocol Elements . . . . . . . . . . . . . . . . . . . . . . 12 82 5.1. IS-IS TLVs . . . . . . . . . . . . . . . . . . . . . . . 12 83 5.1.1. IS-IS Area Leader Sub-TLV . . . . . . . . . . . . . . 12 84 5.1.2. IS-IS Dynamic Flooding Sub-TLV . . . . . . . . . . . 13 85 5.1.3. IS-IS Area Node IDs TLV . . . . . . . . . . . . . . . 14 86 5.1.4. IS-IS Flooding Path TLV . . . . . . . . . . . . . . . 15 87 5.1.5. IS-IS Flooding Request TLV . . . . . . . . . . . . . 16 88 5.1.6. IS-IS LEEF Advertisement . . . . . . . . . . . . . . 18 89 5.2. OSPF LSAs and TLVs . . . . . . . . . . . . . . . . . . . 18 90 5.2.1. OSPF Area Leader Sub-TLV . . . . . . . . . . . . . . 18 91 5.2.2. OSPF Dynamic Flooding Sub-TLV . . . . . . . . . . . . 19 92 5.2.3. OSPFv2 Dynamic Flooding Opaque LSA . . . . . . . . . 19 93 5.2.4. OSPFv3 Dynamic Flooding LSA . . . . . . . . . . . . . 21 94 5.2.5. OSPF Area Router ID TLVs . . . . . . . . . . . . . . 22 95 5.2.5.1. OSPFv2 Area Router ID TLV . . . . . . . . . . . . 22 96 5.2.5.2. OSPFv3 Area Router ID TLV . . . . . . . . . . . . 24 97 5.2.6. OSPF Flooding Path TLV . . . . . . . . . . . . . . . 26 98 5.2.7. OSPF Flooding Request Bit . . . . . . . . . . . . . . 27 99 5.2.8. OSPF LEEF Advertisement . . . . . . . . . . . . . . . 28 100 6. Behavioral Specification . . . . . . . . . . . . . . . . . . 29 101 6.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 29 102 6.2. Flooding Topology . . . . . . . . . . . . . . . . . . . . 29 103 6.3. Leader Election . . . . . . . . . . . . . . . . . . . . . 29 104 6.4. Area Leader Responsibilities . . . . . . . . . . . . . . 30 105 6.5. Distributed Flooding Topology Calculation . . . . . . . . 30 106 6.6. Use of LANs in the Flooding Topology . . . . . . . . . . 31 107 6.6.1. Use of LANs in Centralized mode . . . . . . . . . . . 31 108 6.6.2. Use of LANs in Distributed Mode . . . . . . . . . . . 31 109 6.6.2.1. Partial flooding on a LAN in IS-IS . . . . . . . 31 110 6.6.2.2. Partial Flooding on a LAN in OSPF . . . . . . . . 32 111 6.7. Flooding Behavior . . . . . . . . . . . . . . . . . . . . 32 112 6.8. Treatment of Topology Events . . . . . . . . . . . . . . 33 113 6.8.1. Temporary Addition of Link to Flooding Topology . . . 33 114 6.8.2. Local Link Addition . . . . . . . . . . . . . . . . . 34 115 6.8.3. Node Addition . . . . . . . . . . . . . . . . . . . . 35 116 6.8.4. Failures of Link Not on Flooding Topology . . . . . . 35 117 6.8.5. Failures of Link On the Flooding Topology . . . . . . 35 118 6.8.6. Node Deletion . . . . . . . . . . . . . . . . . . . . 36 119 6.8.7. Local Link Addition to the Flooding Topology . . . . 36 120 6.8.8. Local Link Deletion from the Flooding Topology . . . 36 121 6.8.9. Treatment of Disconnected Adjacent Nodes . . . . . . 37 122 6.8.10. Failure of the Area Leader . . . . . . . . . . . . . 37 123 6.8.11. Recovery from Multiple Failures . . . . . . . . . . . 37 124 6.8.12. Rate Limiting Temporary Flooding . . . . . . . . . . 38 125 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 38 126 7.1. IS-IS . . . . . . . . . . . . . . . . . . . . . . . . . . 38 127 7.2. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . 39 128 7.2.1. OSPF Dynamic Flooding LSA TLVs Registry . . . . . . . 41 129 7.2.2. OSPF Link Attributes Sub-TLV Bit Values Registry . . 41 130 7.3. IGP . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 131 8. Security Considerations . . . . . . . . . . . . . . . . . . . 42 132 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 43 133 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 43 134 10.1. Normative References . . . . . . . . . . . . . . . . . . 43 135 10.2. Informative References . . . . . . . . . . . . . . . . . 45 136 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 45 138 1. Introduction 140 In recent years, there has been increased focus on how to address the 141 dynamic routing of networks that have a bipartite (a.k.a. spine-leaf 142 or leaf-spine), Clos [Clos], or Fat Tree [Leiserson] topology. 143 Conventional Interior Gateway Protocols (IGPs, i.e., IS-IS 144 [ISO10589], OSPFv2 [RFC2328], and OSPFv3 [RFC5340]) under-perform, 145 redundantly flooding information throughout the dense topology, 146 leading to overloaded control plane inputs and thereby creating 147 operational issues. For practical considerations, network architects 148 have resorted to applying unconventional techniques to address the 149 problem, e.g., applying BGP in the data center [RFC7938]. However it 150 is very clear that using an Exterior Gateway Protocol as an IGP is 151 sub-optimal, if only due to the configuration overhead. 153 The primary issue that is demonstrated when conventional mechanisms 154 are applied is the poor reaction of the network to topology changes. 155 Normal link state routing protocols rely on a flooding algorithm for 156 state distribution within an area. In a dense topology, this 157 flooding algorithm is highly redundant, resulting in unnecessary 158 overhead. Each node in the topology receives each link state update 159 multiple times. Ultimately, all of the redundant copies will be 160 discarded, but only after they have reached the control plane and 161 been processed. This creates issues because significant link state 162 database updates can become queued behind many redundant copies of 163 another update. This delays convergence as the link state database 164 does not stabilize promptly. 166 In a real world implementation, the packet queues leading to the 167 control plane are necessarily of finite size, so if the flooding rate 168 exceeds the update processing rate for long enough, the control plane 169 will be obligated to drop incoming updates. If these lost updates 170 are of significance, this will further delay stabilization of the 171 link state database and the convergence of the network. 173 This is not a new problem. Historically, when routing protocols have 174 been deployed in networks where the underlying topology is a complete 175 graph, there have been similar issues. This was more common when the 176 underlying link layer fabric presented the network layer with a full 177 mesh of virtual connections. This was addressed by reducing the 178 flooding topology through IS-IS Mesh Groups [RFC2973], but this 179 approach requires careful configuration of the flooding topology. 181 Thus, the root problem is not limited to massively scalable data 182 centers. It exists with any dense topology at scale. 184 This problem is not entirely surprising. Link state routing 185 protocols were conceived when links were very expensive and 186 topologies were sparse. The fact that those same designs are sub- 187 optimal in a dense topology should not come as a huge surprise. The 188 fundamental premise that was addressed by the original designs was an 189 environment of extreme cost and scarcity. Technology has progressed 190 to the point where links are cheap and common. This represents a 191 complete reversal in the economic fundamentals of network 192 engineering. The original designs are to be commended for continuing 193 to provide correct operation to this point, and optimizations for 194 operation in today's environment are to be expected. 196 1.1. Requirements Language 198 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 199 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 200 document are to be interpreted as described in RFC 2119 [RFC2119]. 202 2. Problem Statement 204 In a dense topology, the flooding algorithm that is the heart of 205 conventional link state routing protocols causes a great deal of 206 redundant messaging. This is exacerbated by scale. While the 207 protocol can survive this combination, the redundant messaging is 208 unnecessary overhead and delays convergence. Thus, the problem is to 209 provide routing in dense, scalable topologies with rapid convergence. 211 3. Solution Requirements 213 A solution to this problem must then meet the following requirements: 215 Requirement 1 Provide a dynamic routing solution. Reachability 216 must be restored after any topology change. 218 Requirement 2 Provide a significant improvement in convergence. 220 Requirement 3 The solution should address a variety of dense 221 topologies. Just addressing a complete bipartite topology such 222 as K5,8 is insufficient. Multi-stage Clos topologies must also 223 be addressed, as well as topologies that are slight variants. 224 Addressing complete graphs is a good demonstration of generality. 226 Requirement 4 There must be no single point of failure. The loss 227 of any link or node should not unduly hinder convergence. 229 Requirement 5 Dense topologies are subgraphs of much larger 230 topologies. Operational efficiency requires that the dense 231 subgraph not operate in a radically different manner than the 232 remainder of the topology. While some operational differences 233 are permissible, they should be minimized. Changes to nodes 234 outside of the dense subgraph are not acceptable. These 235 situations occur when massively scaled data centers are part of 236 an overall larger wide-area network. Having a second protocol 237 operating just on this subgraph would add much more complexity at 238 the edge of the subgraph where the two protocols would have to 239 inter-operate. 241 4. Dynamic Flooding 243 We have observed that the combination of the dense topology and 244 flooding on the physical topology in a scalable network is sub- 245 optimal. However, if we decouple the flooding topology from the 246 physical topology and only flood on a greatly reduced portion of that 247 topology, we can have efficient flooding and retain all of the 248 resilience of existing protocols. A node that supports flooding on 249 the decoupled flooding topology is said to support dynamic flooding. 251 In this idea, the flooding topology is computed within an IGP area 252 with the dense topology either centrally on an elected node, termed 253 the Area Leader, or in a distributed manner on all nodes that are 254 supporting Dynamic Flooding. If the flooding topology is computed 255 centrally, it is encoded into and distributed as part of the normal 256 link state database. We call this the centralized mode of operation. 257 If the flooding topology is computed in a distributed fashion, we 258 call this the distributed mode of operation. Nodes within such an 259 IGP area would only flood on the flooding topology. On links outside 260 of the normal flooding topology, normal database synchronization 261 mechanisms (i.e., OSPF database exchange, IS-IS CSNPs) would apply, 262 but flooding may not. Details are described in Section 6. New link 263 state information that arrives from outside of the flooding topology 264 suggests that the sender has a different or no flooding topology 265 information and that the link state update should be flooded on the 266 flooding topology as well. 268 The flooding topology covers the full set of nodes within the area, 269 but excludes some of the links that standard flooding would employ. 271 Since the flooding topology is computed prior to topology changes, it 272 does not factor into the convergence time and can be done when the 273 topology is stable. The speed of the computation and its 274 distribution, in the case of a centralized mode, is not a significant 275 issue. 277 If a node does not have any flooding topology information when it 278 receives new link state information, it should flood according to 279 standard flooding rules. This situation will occur when the dense 280 topology is first established, but is unlikely to recur. 282 When centralized mode is used and if, during a transient, there are 283 multiple flooding topologies being advertised, then nodes should 284 flood link state updates on all of the flooding topologies. Each 285 node should locally evaluate the election of the Area Leader for the 286 IGP area and first flood on its flooding topology. The rationale 287 behind this is straightforward: if there is a transient and there has 288 been a recent change in Area Leader, then propagating topology 289 information promptly along the most likely flooding topology should 290 be the priority. 292 During transients, it is possible that loops will form in the 293 flooding topology. This is not problematic, as the legacy flooding 294 rules would cause duplicate updates to be ignored. Similarly, during 295 transients, it is possible that the flooding topology may become 296 disconnected. Section 6.8.11 discusses how such conditions are 297 handled. 299 4.1. Applicability 301 In a complete graph, this approach is appealing because it 302 drastically decreases the flooding topology without the manual 303 configuration of mesh groups. By controlling the diameter of the 304 flooding topology, as well as the maximum degree node in the flooding 305 topology, convergence time goals can be met and the stability of the 306 control plane can be assured. 308 Similarly, in a massively scaled data center, where there are many 309 opportunities for redundant flooding, this mechanism ensures that 310 flooding is redundant, with each leaf and spine well connected, while 311 ensuring that no update need make too many hops and that no node 312 shares an undue portion of the flooding effort. 314 In a network where only a portion of the nodes support Dynamic 315 Flooding, the remaining nodes will continue to perform standard 316 flooding. This is not an issue for correctness, as no node can 317 become isolated. 319 Flooding that is initiated by nodes that support Dynamic Flooding 320 will remain within the flooding topology until it reaches a legacy 321 node, which will resume legacy flooding. Standard flooding will be 322 bounded by nodes supporting Dynamic Flooding, which can help limit 323 the propagation of unnecessary flooding. Whether or not the network 324 can remain stable in this condition is unknown and may be very 325 dependent on the number and location of the nodes that support 326 Dynamic Flooding. 328 During incremental deployment of dynamic flooding an area will 329 consist of one or more sets of connected nodes that support dynamic 330 flooding and one or more sets of connected nodes that do not, i.e., 331 nodes that support standard flooding. The flooding topology is the 332 union of these sets of nodes. Each set of nodes that does not 333 support dynamic flooding needs to be part of the flooding topology 334 and such a set of nodes may provide connectivity between two or more 335 sets of nodes that support dynamic flooding. 337 4.2. Leader election 339 A single node within the dense topology is elected as an Area Leader. 341 A generalization of the mechanisms used in existing Designated Router 342 (OSPF) or Designated Intermediate-System (IS-IS) elections suffices. 343 The elected node is known as the Area Leader. 345 In the case of centralized mode, the Area Leader is responsible for 346 computing and distributing the flooding topology. When a new Area 347 Leader is elected and has distributed new flooding topology 348 information, then any prior Area Leaders should withdraw any of their 349 flooding topology information from their link state database entries. 351 In the case of distributed mode, the distributed algorithm advertised 352 by the Area Leader MUST be used by all nodes that participate in 353 Dynamic Flooding. 355 Not every node needs to be a candidate to be Area Leader within an 356 area, as a single candidate is sufficient for correct operation. For 357 redundancy, however, it is strongly RECOMMENDED that there be 358 multiple candidates. 360 4.3. Computing the Flooding Topology 362 There is a great deal of flexibility in how the flooding topology may 363 be computed. For resilience, it needs to at least contain a cycle of 364 all nodes in the dense subgraph. However, additional links could be 365 added to decrease the convergence time. The trade-off between the 366 density of the flooding topology and the convergence time is a matter 367 for further study. The exact algorithm for computing the flooding 368 topology in the case of the centralized computation need not be 369 standardized, as it is not an interoperability issue. Only the 370 encoding of the result needs to be documented. In the case of 371 distributed mode, all nodes in the IGP area need to use the same 372 algorithm to compute the flooding topology. It is possible to use 373 private algorithms to compute flooding topology, so long as all nodes 374 in the IGP area use the same algorithm. 376 While the flooding topology should be a covering cycle, it need not 377 be a Hamiltonian cycle where each node appears only once. In fact, 378 in many relevant topologies this will not be possible e.g., K5,8. 379 This is fortunate, as computing a Hamiltonian cycle is known to be 380 NP-complete. 382 A simple algorithm to compute the topology for a complete bipartite 383 graph is to simply select unvisited nodes on each side of the graph 384 until both sides are completely visited. If the number of nodes on 385 each side of the graph are unequal, then revisiting nodes on the less 386 populated side of the graph will be inevitable. This algorithm can 387 run in O(N) time, so is quite efficient. 389 While a simple cycle is adequate for correctness and resiliency, it 390 may not be optimal for convergence. At scale, a cycle may have a 391 diameter that is half the number of nodes in the graph. This could 392 cause an undue delay in link state update propagation. Therefore it 393 may be useful to have a bound on the diameter of the flooding 394 topology. Introducing more links into the flooding topology would 395 reduce the diameter, but at the trade-off of possibly adding 396 redundant messaging. The optimal trade-off between convergence time 397 and graph diameter is for further study. 399 Similarly, if additional redundancy is added to the flooding 400 topology, specific nodes in that topology may end up with a very high 401 degree. This could result in overloading the control plane of those 402 nodes, resulting in poor convergence. Thus, it may be optimal to 403 have an upper bound on the degree of nodes in the flooding topology. 404 Again, the optimal trade-off between graph diameter, node degree, and 405 convergence time, and topology computation time is for further study. 407 If the leader chooses to include a multi-node broadcast LAN segment 408 as part of the flooding topology, all of the connectivity to that LAN 409 segment should be included as well. Once updates are flooded onto 410 the LAN, they will be received by every attached node. 412 4.4. Topologies on Complete Bipartite Graphs 414 Complete bipartite graph topologies have become popular for data 415 center applications and are commonly called leaf-spine or spine-leaf 416 topologies. In this section, we discuss some flooding topologies 417 that are of particular interest in these networks. 419 4.4.1. A Minimal Flooding Topology 421 We define a Minimal Flooding Topology on a complete bipartite graph 422 as one in which the topology is connected and each node has at least 423 degree two. This is of interest because it guarantees that the 424 flooding topology has no single points of failure. 426 In practice, this implies that every leaf node in the flooding 427 topology will have a degree of two. As there are usually more leaves 428 than spines, the degree of the spines will be higher, but the load on 429 the individual spines can be evenly distributed. 431 This type of flooding topology is also of interest because it scales 432 well. As the number of leaves increases, we can construct flooding 433 topologies that perform well. Specifically, for n spines and m 434 leaves, if m >= n(n/2-1), then there is a flooding topology that has 435 a diameter of four. 437 4.4.2. Xia Topologies 439 We define a Xia Topology on a complete bipartite graph as one in 440 which all spine nodes are bi-connected through leaves with degree 441 two, but the remaining leaves all have degree one and are evenly 442 distributed across the spines. 444 Constructively, we can create a Xia topology by iterating through the 445 spines. Each spine can be connected to the next spine by selecting 446 any unused leaf. Since leaves are connected to all spines, all 447 leaves will have a connection to both the first and second spine and 448 we can therefore choose any leaf without loss of generality. 449 Continuing this iteration across all of the spines, selecting a new 450 leaf at each iteration, will result in a path that connects all 451 spines. Adding one more leaf between the last and first spine will 452 produce a cycle of n spines and n leaves. 454 At this point, m-n leaves remain unconnected. These can be 455 distributed evenly across the remaining spines, connected by a single 456 link. 458 Xia topologies represent a compromise that trades off increased risk 459 and decreased performance for lower flooding amplification. Xia 460 topologies will have a larger diameter. For m spines, the diameter 461 will be m + 2. 463 In a Xia topology, some leaves are singly connected. This represents 464 a risk in that in some failures, convergence may be delayed. 465 However, there may be some alternate behaviors that can be employed 466 to mitigate these risks. If a leaf node sees that its single link on 467 the flooding topology has failed, it can compensate by performing a 468 database synchronization check with a different spine. Similarly, if 469 a leaf determines that its connected spine on the flooding topology 470 has failed, it can compensate by performing a database 471 synchronization check with a different spine. In both of these 472 cases, the synchronization check is intended to ameliorate any delays 473 in link state propagation due to the fragmentation of the flooding 474 topology. 476 The benefit of this topology is that flooding load is easily 477 understood. Each node in the spine cycle will never receive an 478 update more than twice. For m leaves and n spines, a spine never 479 transmits more than (m/n +1) updates. 481 4.4.3. Optimization 483 If two nodes are adjacent on the flooding topology and there are a 484 set of parallel links between them, then any given update MUST be 485 flooded over a single one of those links. Selection of the specific 486 link is implementation specific. 488 4.5. Encoding the Flooding Topology 490 There are a variety of ways that the flooding topology could be 491 encoded efficiently. If the topology was only a cycle, a simple list 492 of the nodes in the topology would suffice. However, this is 493 insufficiently flexible as it would require a slightly different 494 encoding scheme as soon as a single additional link is added. 495 Instead, we choose to encode the flooding topology as a set of 496 intersecting paths, where each path is a set of connected edges. 498 Advertisement of the flooding topology includes support for multi- 499 access LANs. When a LAN is included in the flooding topology, all 500 edges between the LAN and nodes connected to the LAN are assumed to 501 be part of the flooding topology. In order to reduce the size of the 502 flooding topology advertisement, explicit advertisement of these 503 edges is optional. Note that this may result in the possibility of 504 "hidden nodes" existing which are actually part of the flooding 505 topology but which are not explicitly mentioned in the flooding 506 topology advertisements. These hidden nodes can be found by 507 examination of the Link State database where connectivity between a 508 LAN and nodes connected to the LAN is fully specified. 510 Note that while all nodes MUST be part of the advertised flooding 511 topology not all multi-access LANs need to be included. Only those 512 LANs which are part of the flooding topology need to be included in 513 the advertised flooding topology. 515 Other encodings are certainly possible. We have attempted to make a 516 useful trade off between simplicity, generality, and space. 518 4.6. Advertising the Local Edges Enabled for Flooding 520 Correct operation of the flooding topology requires that all nodes 521 which participate in the flooding topology choose local links for 522 flooding which are consistent with the calculated flooding topology. 523 Failure to do so could result in unexpected partition of the flooding 524 topology and/or sub-optimal flooding reduction. As an aid to 525 diagnosing problems when dynamic flooding is in use, this document 526 defines a means of advertising what local edges are enabled for 527 flooding (LEEF). The protocol specific encodings are defined in 528 Sections 5.1.6 and 5.2.8. 530 The following guidelines apply: 532 Advertisement of LEEFs is optional. 534 As the flooding topology is defined by edges (not by links), in 535 cases where parallel adjacencies to the same neighbor exist, the 536 advertisement SHOULD indicate that all such links have been 537 enabled. 539 LEEF advertisements MUST NOT include edges enabled for temporary 540 flooding (Section 6.7). 542 LEEF advertisements MUST NOT be used either when calculating a 543 flooding topology or when determining what links to add 544 temporarily to the flooding topology when the flooding topology is 545 temporarily partitioned. 547 5. Protocol Elements 549 5.1. IS-IS TLVs 551 The following TLVs/sub-TLVs are added to IS-IS: 553 1. A sub-TLV that an IS may inject into its LSP to indicate its 554 preference for becoming Area Leader. 556 2. A sub-TLV that an IS may inject into its LSP to indicate that it 557 supports Dynamic Flooding and the algorithms that it supports for 558 distributed mode, if any. 560 3. A TLV to carry the list of system IDs that compromise the 561 flooding topology for the area. 563 4. A TLV to carry a path which is part of the flooding topology 565 5. A TLV that requests flooding from the adjacent node 567 5.1.1. IS-IS Area Leader Sub-TLV 569 The Area Leader Sub-TLV allows a system to: 571 1. Indicate its eligibility and priority for becoming Area Leader. 573 2. Indicate whether centralized or distributed mode is to be used to 574 compute the flooding topology in the area. 576 3. Indicate the algorithm identifier for the algorithm that is used 577 to compute the flooding topology in distributed mode. 579 Intermediate Systems (nodes) that are not advertising this Sub-TLV 580 are not eligible to become Area Leader. 582 The Area Leader is the node with the numerically highest Area Leader 583 priority in the area. In the event of ties, the node with the 584 numerically highest system ID is the Area Leader. Due to transients 585 during database flooding, different nodes may not agree on the Area 586 Leader. 588 The Area Leader Sub-TLV is advertised as a Sub-TLV of the IS-IS 589 Router Capability TLV-242 that is defined in [RFC7981] and has the 590 following format: 592 0 1 2 3 593 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 594 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 595 | Type | Length | Priority | Algorithm | 596 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 598 Type: TBD1 600 Length: 2 602 Priority: 0-255, unsigned integer 604 Algorithm: a numeric identifier in the range 0-255 that identifies 605 the algorithm used to calculate the flooding topology. The 606 following values are defined: 608 0: Centralized computation by the Area Leader. 610 1-127: Standardized distributed algorithms. Individual values 611 are are to be assigned according to the "Specification 612 Required" policy defined in [RFC8126] (see Section 7.3). 614 128-254: Private distributed algorithms. Individual values are 615 are to be assigned according to the "Private Use" policy 616 defined in [RFC8126] (see Section 7.3). 618 255: Reserved 620 5.1.2. IS-IS Dynamic Flooding Sub-TLV 622 The Dynamic Flooding Sub-TLV allows a system to: 624 1. Indicate that it supports Dynamic Flooding. This is indicated by 625 the advertisement of this Sub-TLV. 627 2. Indicate the set of algorithms that it supports for distributed 628 mode, if any. 630 In incremental deployments, understanding which nodes support Dynamic 631 Flooding can be used to optimize the flooding topology. In 632 distributed mode, knowing the capabilities of the nodes can allow the 633 Area Leader to select the optimal algorithm. 635 The Dynamic Flooding Sub-TLV is advertised as a Sub-TLV of the IS-IS 636 Router Capability TLV (242) [RFC7981] and has the following format: 638 0 1 2 3 639 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 640 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 641 | Type | Length | Algorithm... | 642 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 644 Type: TBD7 646 Length: 0-255; number of Algorithms 648 Algorithm: zero or more numeric identifiers in the range 0-255 649 that identifies the algorithm used to calculate the flooding 650 topology, as described in Section 5.1.1. 652 5.1.3. IS-IS Area Node IDs TLV 654 The IS-IS Area Node IDs TLV is only used in centralized mode. 656 The Area Node IDs TLV is used by the Area Leader to enumerate the 657 Node IDs (System ID + pseudo-node ID) that it has used in computing 658 the area flooding topology. Conceptually, the Area Leader creates a 659 list of node IDs for all nodes in the area (including pseudo-nodes 660 for all LANs in the topology), assigning indices to each node, 661 starting with index 0. 663 Because the space in a single TLV is limited, more than one TLV may 664 be required to encode all of the node IDs in the area. This TLV may 665 be present in multiple LSPs. 667 The format of the Area Node IDs TLV is: 669 0 1 2 3 670 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 671 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 672 | Type | Length | Starting Index | 673 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 674 |L| Reserved | Node IDs ... 675 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 676 Node IDs continued .... 677 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 679 Type: TBD2 681 Length: 3 + ((System ID Length + 1) * (number of node IDs)) 683 Starting index: The index of the first node ID that appears in 684 this TLV. 686 L (Last): This bit is set if the index of the last node ID that 687 appears in this TLV is equal to the last index in the full list of 688 node IDs for the area. 690 Node IDs: A concatenated list of node IDs for the area 692 If there are multiple IS-IS Area Node IDs TLVs with the L bit set 693 advertised by the same node, the TLV which specifies the smaller 694 maximum index is used and the other TLV(s) with L bit set are 695 ignored. TLVs which specify node IDs with indices greater than that 696 specified by the TLV with the L bit set are also ignored. 698 5.1.4. IS-IS Flooding Path TLV 700 IS-IS Flooding Path TLV is only used in centralized mode. 702 The Flooding Path TLV is used to denote a path in the flooding 703 topology. The goal is an efficient encoding of the links of the 704 topology. A single link is a simple case of a path that only covers 705 two nodes. A connected path may be described as a sequence of 706 indices: (I1, I2, I3, ...), denoting a link from the system with 707 index 1 to the system with index 2, a link from the system with index 708 2 to the system with index 3, and so on. 710 If a path exceeds the size that can be stored in a single TLV, then 711 the path may be distributed across multiple TLVs by the replication 712 of a single system index. 714 Complex topologies that are not a single path can be described using 715 multiple TLVs. 717 The Flooding Path TLV contains a list of system indices relative to 718 the systems advertised through the Area Node IDs TLV. At least 2 719 indices must be included in the TLV. Due to the length restriction 720 of TLVs, this TLV can contain at most 126 system indices. 722 The Flooding Path TLV has the format: 724 0 1 2 3 725 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 726 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 727 | Type | Length | Starting Index | 728 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 729 | Index 2 | Additional indices ... 730 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 732 Type: TBD3 734 Length: 2 * (number of indices in the path) 736 Starting index: The index of the first system in the path. 738 Index 2: The index of the next system in the path. 740 Additional indices (optional): A sequence of additional indices to 741 systems along the path. 743 5.1.5. IS-IS Flooding Request TLV 745 The Flooding Request TLV allows a system to request an adjacent node 746 to enable flooding towards it on a specific link in the case where 747 the connection to adjacent node is not part of the existing flooding 748 topology. 750 Nodes that support Dynamic Flooding MAY include the Flooding Request 751 TLV in its IIH PDUs. 753 The Flooding Request TLV has the format: 755 0 1 2 3 756 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 757 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 758 | Type | Length | Levels |R| Scope | 759 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 760 |R| ... | 761 -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 763 Type: TBD9 764 Length: 1 + number of advertised Flooding Scopes 766 Levels - the level(s) for which flooding is requested. Levels are 767 encoded as the circuit type specified in IS-IS [ISO10589] 769 R bit: MUST be 0 and is ignored on receipt. 771 Scope: Flooding Scope for which the flooding is requested as 772 defined by LSP Flooding Scope Identifier Registry defined by 773 [RFC7356]. Inclusion of flooding scopes is optional and is only 774 necessary if [RFC7356] is supported. Multiple flooding scopes MAY 775 be included. 777 Circuit Flooding Scope MUST NOT be sent in the Flooding Request TLV 778 and MUST be ignored if received. 780 When the TLV is received in a level specific LAN-Hello PDU (L1-LAN- 781 IIH or L2-LAN-IIH) only levels which match the PDU type are valid. 782 Levels which do not match the PDU type MUST be ignored on receipt. 784 When the TLV is received in a Point-to-Point Hello (P2P-IIH) only 785 levels which are supported by the established adjacency are valid. 786 Levels which are not supported by the adjacency MUST be ignored on 787 receipt. 789 If flooding was disabled on the received link due to Dynamic 790 Flooding, then flooding MUST be temporarily enabled over the link for 791 the specified Circuit Type(s) and Flooding Scope(s) received in the 792 in the Flooding Request TLV. Flooding MUST be enabled until the 793 Circuit Type or Flooding Scope is no longer advertised in the 794 Flooding Request TLV or the TLV no longer appears in IIH PDUs 795 received on the link. 797 When the flooding is temporarily enabled on the link for any Circuit 798 Type or Flooding Scope due to received Flooding Request TLV, the 799 receiver MUST perform standard database synchronization for the 800 corresponding Circuit Type(s) and Flooding Scope(s) on the link. In 801 the case of IS-IS, this results in setting SRM bit for all related 802 LSPs on the link and sending CSNPs. 804 So long as the Flooding Request TLV is being received flooding MUST 805 NOT be disabled for any of the Circuit Types or Flooding Scopes 806 present in the Flooding Request TLV even if the connection between 807 the neighbors is removed from the flooding topology. Flooding for 808 such Circuit Types or Flooding Scopes MUST continue on the link and 809 be considered as temporarily enabled. 811 5.1.6. IS-IS LEEF Advertisement 813 In support of advertising which edges are currently enabled in the 814 flooding topology, an implementation MAY indicate that a link is part 815 of the flooding topology by advertising a bit value in the Link 816 Attributes sub-TLV defined by [RFC5029]. 818 The following bit value is defined by this document: 820 Local Edge Enabled for Flooding (LEEF) - suggested value 4 (to be 821 assigned by IANA) 823 5.2. OSPF LSAs and TLVs 825 This section defines new LSAs and TLVs for both OSPFv2 and OSPFv3. 827 Following objects are added: 829 1. A TLV that is used to advertise the preference for becoming Area 830 Leader. 832 2. A TLV that is used to indicate the support for Dynamic Flooding 833 and the algorithms that the advertising node supports for 834 distributed mode, if any. 836 3. OSPFv2 Opaque LSA and OSPFv3 LSA to advertise the flooding 837 topology for centralized mode. 839 4. A TLV to carry the list of Router IDs that comprise the flooding 840 topology for the area. 842 5. A TLV to carry a path which is part of the flooding topology. 844 6. The bit in the LLS Type 1 Extended Options and Flags requests 845 flooding from the adjacent node. 847 5.2.1. OSPF Area Leader Sub-TLV 849 The usage of the OSPF Area Leader Sub-TLV is identical to IS-IS and 850 is described in Section 5.1.1. 852 The OSPF Area Leader Sub-TLV is used by both OSPFv2 and OSPFv3. 854 The OSPF Area Leader Sub-TLV is advertised as a top-level TLV of the 855 RI LSA that is defined in [RFC7770] and has the following format: 857 0 1 2 3 858 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 859 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 860 | Type | Length | 861 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 862 | Priority | Algorithm | Reserved | 863 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 865 Type: TBD4 867 Length: 4 octets 869 Priority: 0-255, unsigned integer 871 Algorithm: as defined in Section 5.1.1. 873 5.2.2. OSPF Dynamic Flooding Sub-TLV 875 The usage of the OSPF Dynamic Flooding Sub-TLV is identical to IS-IS 876 and is described in Section 5.1.2. 878 The OSPF Dynamic Flooding Sub-TLV is used by both OSPFv2 and OSPFv3. 880 The OSPF Dynamic Flooding Sub-TLV is advertised as a top-level TLV of 881 the RI LSA that is defined in [RFC7770] and has the following format: 883 0 1 2 3 884 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 885 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 886 | Type | Length | 887 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 888 | Algorithm ... | | 889 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 891 Type: TBD8 893 Length: number of Algorithms 895 Algorithm: as defined in Section 5.1.1. 897 5.2.3. OSPFv2 Dynamic Flooding Opaque LSA 899 The OSPFv2 Dynamic Flooding Opaque LSA is only used in centralized 900 mode. 902 The OSPFv2 Dynamic Flooding Opaque LSA is used to advertise 903 additional data related to the dynamic flooding in OSPFv2. OSPFv2 904 Opaque LSAs are described in [RFC5250]. 906 Multiple OSPFv2 Dynamic Flooding Opaque LSAs can be advertised by an 907 OSPFv2 router. The flooding scope of the OSPFv2 Dynamic Flooding 908 Opaque LSA is area-local. 910 The format of the OSPFv2 Dynamic Flooding Opaque LSA is as follows: 912 0 1 2 3 913 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 914 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 915 | LS age | Options | LS Type | 916 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 917 | TBD5 | Opaque ID | 918 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 919 | Advertising Router | 920 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 921 | LS sequence number | 922 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 923 | LS checksum | Length | 924 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 925 | | 926 +- TLVs -+ 927 | ... | 929 OSPFv2 Dynamic Flooding Opaque LSA 931 The opaque type used by OSPFv2 Dynamic Flooding Opaque LSA is TBD. 932 The opaque type is used to differentiate the various type of OSPFv2 933 Opaque LSAs and is described in section 3 of [RFC5250]. The LS Type 934 is 10. The LSA Length field [RFC2328] represents the total length 935 (in octets) of the Opaque LSA including the LSA header and all TLVs 936 (including padding). 938 The Opaque ID field is an arbitrary value used to maintain multiple 939 Dynamic Flooding Opaque LSAs. For OSPFv2 Dynamic Flooding Opaque 940 LSAs, the Opaque ID has no semantic significance other than to 941 differentiate Dynamic Flooding Opaque LSAs originated by the same 942 OSPFv2 router. 944 The format of the TLVs within the body of the OSPFv2 Dynamic Flooding 945 Opaque LSA is the same as the format used by the Traffic Engineering 946 Extensions to OSPF [RFC3630]. 948 The Length field defines the length of the value portion in octets 949 (thus a TLV with no value portion would have a length of 0). The TLV 950 is padded to 4-octet alignment; padding is not included in the length 951 field (so a 3-octet value would have a length of 3, but the total 952 size of the TLV would be 8 octets). Nested TLVs are also 32-bit 953 aligned. For example, a 1-octet value would have the length field 954 set to 1, and 3 octets of padding would be added to the end of the 955 value portion of the TLV. The padding is composed of zeros. 957 5.2.4. OSPFv3 Dynamic Flooding LSA 959 The OSPFv3 Dynamic Flooding Opaque LSA is only used in centralized 960 mode. 962 The OSPFv3 Dynamic Flooding LSA is used to advertise additional data 963 related to the dynamic flooding in OSPFv3. 965 The OSPFv3 Dynamic Flooding LSA has a function code of TBD. The 966 flooding scope of the OSPFv3 Dynamic Flooding LSA is area-local. The 967 U bit will be set indicating that the OSPFv3 Dynamic Flooding LSA 968 should be flooded even if it is not understood. The Link State ID 969 (LSID) value for this LSA is the Instance ID. OSPFv3 routers MAY 970 advertise multiple Dynamic Flooding Opaque LSAs in each area. 972 The format of the OSPFv3 Dynamic Flooding LSA is as follows: 974 0 1 2 3 975 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 976 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 977 | LS age |1|0|1| TBD6 | 978 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 979 | Link State ID | 980 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 981 | Advertising Router | 982 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 983 | LS sequence number | 984 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 985 | LS checksum | Length | 986 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 987 | | 988 +- TLVs -+ 989 | ... | 991 OSPFv3 Dynamic Flooding LSA 993 5.2.5. OSPF Area Router ID TLVs 995 In OSPF new TLVs are introduced to advertise indeces associated with 996 nodes and Broadcast/NBMA networks. Due to identifier differences 997 between OSPFv2 and OSPFv3 two different TLVs are defined as decribed 998 in the following sub-sections. 1000 The OSPF Area Router ID TLVs are used by the Area Leader to enumerate 1001 the Router IDs that it has used in computing the flooding topology. 1002 This includes the identifiers associated with Broadcast/NBMA networks 1003 as defined for Network LSAs. Conceptually, the Area Leader creates a 1004 list of Router IDs for all routers in the area, assigning indices to 1005 each router, starting with index 0. 1007 5.2.5.1. OSPFv2 Area Router ID TLV 1009 This TLV is a top level TLV of the OSPFv2 Dynamic Flooding Opaque 1010 LSA. 1012 Because the space in a single OSPFv2 Area Router IDs TLV is limited, 1013 more than one TLV may be required to encode all of the Router IDs in 1014 the area. This TLV may also occur in multiple OSPFv2 Dynamic 1015 Flooding Opaque LSAs so that all Router IDs can be advertised. 1017 Each entry in the OSPFv2 Area Router IDs TLV represents either a node 1018 or a Broadcast/NBMA network identifier. An entry has the following 1019 format: 1021 0 1 2 3 1022 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 1023 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1024 | Conn Type | Number of IDs | Reserved | 1025 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1026 | | 1027 +- Originating Router ID/DR Address -+ 1028 | ... | 1030 where 1032 Conn Type - 1 byte 1033 The following values are defined: 1034 1 - Router 1035 2 - Designated Router 1037 Number of IDs - 2 bytes 1039 Reserved - 1 byte 1040 MUST be transmitted as 0 and MUST be ignored on receipt 1042 Originating Router ID/DR Address - (4 * Number of IDs) bytes 1043 As indicated by the ID Type 1045 OSPFv2 Router IDs TLV Entry 1047 The format of the Area Router IDs TLV is: 1049 0 1 2 3 1050 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 1051 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1052 | Type | Length | 1053 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1054 | Starting Index |L| Flags | Reserved | 1055 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1056 | | 1057 +- OSPFv2 Router ID TLV Entry -+ 1058 | ... | 1060 OSPFv2 Area Router IDs TLV 1062 TLV Type: 1 1064 TLV Length: 4 + (8 * the number TLV entries) 1065 Starting index: The index of the first Router/Designated Router ID 1066 that appears in this TLV. 1068 L (Last): This bit is set if the index of the last Router/ 1069 Designated ID that appears in this TLV is equal to the last index 1070 in the full list of Rourer IDs for the area. 1072 OSPFv2 Router ID TLV Entries: A concatenated list of Router ID TLV 1073 Entries for the area. 1075 If there are multiple OSPFv2 Area Router ID TLVs with the L bit set 1076 advertised by the same router, the TLV which specifies the smaller 1077 maximum index is used and the other TLV(s) with L bit set are 1078 ignored. TLVs which specify Router IDs with indices greater than 1079 that specified by the TLV with the L bit set are also ignored. 1081 5.2.5.2. OSPFv3 Area Router ID TLV 1083 This TLV is a top level TLV of the OSPFv3 Dynamic Flooding LSA. 1085 Because the space in a single OSPFv3 Area Router ID TLV is limited, 1086 more than one TLV may be required to encode all of the Router IDs in 1087 the area. This TLV may also occur in multiple OSPFv3 Dynamic 1088 Flooding Opaque LSAs so that all Router IDs can be advertised. 1090 Each entry in the OSPFv3 Area Router IDs TLV represents either a 1091 router or a Broadcast/NBMA network identifier. An entry has the 1092 following format: 1094 0 1 2 3 1095 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 1096 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1097 | Conn Type | Number of IDs | Reserved | 1098 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1099 | | 1100 +- Originating ID Entry -+ 1101 | ... | 1103 where 1105 Conn Type - 1 byte 1106 The following values are defined: 1107 1 - Router 1108 2 - Designated Router 1110 Number of IDs - 2 bytes 1112 Reserved - 1 byte 1113 MUST be transmitted as 0 and MUST be ignored on receipt 1115 Originating ID Entry takes one of the following forms: 1117 Router: 1118 0 1 2 3 1119 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 1120 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1121 | Originating Router ID | 1122 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1124 Length of Originating ID Entry is 4 * Number of IDs) bytes 1126 Designated Router: 1127 0 1 2 3 1128 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 1129 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1130 | Originating Router ID | 1131 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1132 | Interface ID | 1133 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1135 Length of Originating ID Entry is (8 * Number of IDs) bytes 1137 OSPFv3 Router ID TLV Entry 1139 The format of the OSPFv3Area Router IDs TLV is: 1141 0 1 2 3 1142 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 1143 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1144 | Type | Length | 1145 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1146 | Starting Index |L| Flags | Reserved | 1147 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1148 | | 1149 +- OSPFv3 Router ID TLV Entry -+ 1150 | ... | 1152 OSPFv3 Area Router IDs TLV 1154 TLV Type: 1 1156 TLV Length: 4 + sum of the lengths of all TLV entries 1158 Starting index: The index of the first Router/Designated Router ID 1159 that appears in this TLV. 1161 L (Last): This bit is set if the index of the last Router/ 1162 Designated Router ID that appears in this TLV is equal to the last 1163 index in the full list of Router IDs for the area. 1165 OSPFv3 Router ID TLV Entries: A concatenated list of Router ID TLV 1166 Entries for the area. 1168 If there are multiple OSPFv3 Area Router ID TLVs with the L bit set 1169 advertised by the same router, the TLV which specifies the smaller 1170 maximum index is used and the other TLV(s) with L bit set are 1171 ignored. TLVs which specify Router IDs with indices greater than 1172 that specified by the TLV with the L bit set are also ignored. 1174 5.2.6. OSPF Flooding Path TLV 1176 The OSPF Flooding Path TLV is a top level TLV of the OSPFv2 Dynamic 1177 Flooding Opaque LSAs and OSPFv3 Dynamic Flooding LSA. 1179 The usage of the OSPF Flooding Path TLV is identical to IS-IS and is 1180 described in Section 5.1.4. 1182 The OSPF Flooding Path TLV contains a list of Router ID indices 1183 relative to the Router IDs advertised through the OSPF Area Router 1184 IDs TLV. At least 2 indices must be included in the TLV. 1186 Multiple OSPF Flooding Path TLVs can be advertised in a single OSPFv2 1187 Dynamic Flooding Opaque LSA or OSPFv3 Dynamic Flooding LSA. OSPF 1188 Flooding Path TLVs can also be advertised in multiple OSPFv2 Dynamic 1189 Flooding Opaque LSAs or OSPFv3 Dynamic Flooding LSA, if they all can 1190 not fit in a single LSA. 1192 The Flooding Path TLV has the format: 1194 0 1 2 3 1195 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 1196 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1197 | Type | Length | 1198 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1199 | Starting Index | Index 2 | 1200 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1201 | | 1202 +- Additional Indices -+ 1203 | ... | 1205 OSPF Flooding Path TLV 1207 TLV Type: 2 1209 TLV Length: 2 * (number of indices in the path) 1211 Starting index: The index of the first Router ID in the path. 1213 Index 2: The index of the next Router ID in the path. 1215 Additional indices (optional): A sequence of additional indices to 1216 Router IDs along the path. 1218 5.2.7. OSPF Flooding Request Bit 1220 A single new option bit, the Flooding-Request (FR-bit), is defined in 1221 the LLS Type 1 Extended Options and Flags field [RFC2328]. The FR- 1222 bit allows a router to request an adjacent node to enable flooding 1223 towards it on a specific link in the case where the connection to 1224 adjacent node is not part of the current flooding topology. 1226 Nodes that support Dynamic Flooding MAY include FR-bit in its OSPF 1227 LLS Extended Options and Flags TLV. 1229 If FR-bit is signalled for an area for which the flooding on the link 1230 was disabled due to Dynamic Flooding, the flooding MUST be 1231 temporarily enabled over such link and area. Flooding MUST be 1232 enabled until FR-bit is no longer advertised in the OSPF LLS Extended 1233 Options and Flags TLV or the OSPF LLS Extended Options and Flags TLV 1234 no longer appears in the OSPF Hellos. 1236 When the flooding is temporarily enabled on the link for any area due 1237 to received FR-bit in OSPF LLS Extended Options and Flags TLV, the 1238 receiver MUST perform standard database synchronization for the 1239 corresponding area(s) on the link. If the adjacency is already in 1240 the FULL state, mechanism specified in [RFC4811] MUST be used for 1241 database resynchronization. 1243 So long as the FR-bit is being received in the OSPF LLS Extended 1244 Options and Flags TLV for an area, flooding MUST NOT be disabled in 1245 such area even if the connection between the neighbors is removed 1246 from the flooding topology. Flooding for such area MUST continue on 1247 the link and be considered as temporarily enabled. 1249 5.2.8. OSPF LEEF Advertisement 1251 In support of advertising which edges are currently enabled in the 1252 flooding topology, an implementation MAY indicate that a link is part 1253 of the flooding topology. The OSPF Link Attributes Bits TLV is 1254 defined to support this advertisement. 1256 0 1 2 3 1257 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 1258 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1259 | Type | Length | 1260 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1261 | Link Attribute Bits | 1262 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1263 | | 1264 +- Additional Link Attribute Bits -+ 1265 | ... | 1267 OSPF Link Attributes Bits TLV 1269 Type: TBD and specific to OSPFv2 and OSPFv3 1271 Length: size of the Link Attribute Bits in bytes. It MUST be a 1272 multiple of 4 bytes. 1274 The following bits are defined: 1276 Bit #0: - Local Edge Enabled for Flooding (LEEF) 1278 OSPF Link-attribute Bits TLV appears as: 1280 1. a sub-TLV of the OSPFv2 Extended Link TLV [RFC7684] 1282 2. a sub-TLV of the OSPFv3 Router-Link TLV [RFC8362] 1284 6. Behavioral Specification 1286 In this section, we specify the detailed behaviors of the nodes 1287 participating in the IGP. 1289 6.1. Terminology 1291 We define some terminology here that is used in the following 1292 sections: 1294 A node is considered reachable if it is part of the connected 1295 network graph. Note that this is independent of any constraints 1296 which may be considered when performing IGP SPT calculation (e.g., 1297 link metrics, OL bit state, etc.). Two-way-connectivity check 1298 MUST be performed before including an edge in the connected 1299 network graph. 1301 Node is connected to the flooding topology, if it has at least one 1302 local link, which is part of the flooding topology. 1304 Node is disconnected from the flooding topology when it is not 1305 connected to the flooding topology. 1307 Current flooding topology - latest version of the flooding 1308 topology received (in case of the centralized mode) or calculated 1309 locally (in case of the distributed mode). 1311 6.2. Flooding Topology 1313 The flooding topology MUST include all reachable nodes in the area. 1315 If a node's reachability changes, the flooding topology MUST be 1316 recalculated. In centralized mode, the Area Leader MUST advertise a 1317 new flooding topology. 1319 If a node becomes disconnected from the current flooding topology but 1320 is still reachable then a new flooding topology MUST be calculated. 1321 In centralized mode the Area Leader MUST advertise the new flooding 1322 topology. 1324 The flooding topology SHOULD be bi-connected. 1326 6.3. Leader Election 1328 Any node that is capable MAY advertise its eligibility to become Area 1329 Leader. 1331 Nodes that are not reachable are not eligible as Area Leader. Nodes 1332 that do not advertise their eligibility to become Area Leader are not 1333 eligible. Amongst the eligible nodes, the node with the numerically 1334 highest priority is the Area Leader. If multiple nodes all have the 1335 highest priority, then the node with the numerically highest system 1336 identifier in the case of IS-IS, or Router-ID in the case of OSPFv2 1337 and OSPFv3 is the Area Leader. 1339 6.4. Area Leader Responsibilities 1341 If the Area Leader operates in centralized mode, it MUST advertise 1342 algorithm 0 in its Area Leader Sub-TLV. In order for Dynamic 1343 Flooding to be enabled it also MUST compute and advertise a flooding 1344 topology for the area. The Area Leader may update the flooding 1345 topology at any time, however, it should not destabilize the network 1346 with undue or overly frequent topology changes. If the Area Leader 1347 operates in centralized mode and needs to advertise a new flooding 1348 topology, it floods the new flooding topology on both the new and old 1349 flooding topologies. 1351 If the Area Leader operates in distributed mode, it MUST advertise a 1352 non-zero algorithm in its Area Leader Sub-TLV. 1354 When the Area Leader advertises algorithm 0 in its Area Leader Sub- 1355 TLV and does not advertise a flooding topology, Dynamic Flooding is 1356 disabled for the area. Note this applies whether the Area Leader 1357 intends to operate in centralized mode or in distributed mode. 1359 Note that once Dynamic Flooding is enabled, disabling it risks 1360 destabilizing the network. 1362 6.5. Distributed Flooding Topology Calculation 1364 If the Area Leader advertises a non-zero algorithm in its Area Leader 1365 Sub-TLV, all nodes in the area that support Dynamic Flooding and the 1366 value of algorithm advertised by the Area Leader MUST compute the 1367 flooding topology based on the Area Leader's advertised algorithm. 1369 Nodes that do not support the value of algorithm advertised by the 1370 Area Leader MUST continue to use standard flooding mechanism as 1371 defined by the protocol. 1373 Nodes that do not support the value of algorithm advertised by the 1374 Area Leader MUST be considered as Dynamic Flooding incapable nodes by 1375 the Area Leader. 1377 If the value of the algorithm advertised by the Area Leader is from 1378 the range 128-254 (private distributed algorithms), it is the 1379 responsibility of the network operator to guarantee that all nodes in 1380 the area have a common understanding of what the given algorithm 1381 value represents. 1383 6.6. Use of LANs in the Flooding Topology 1385 Use of LANs in the flooding topology differs depending on whether the 1386 area is operating in Centralized or Distributed mode. 1388 6.6.1. Use of LANs in Centralized mode 1390 As specified in Section 4.5, when a LAN is advertised as part of the 1391 flooding topology, all nodes connected to the LAN are assumed to be 1392 using the LAN as part of the flooding topology. This assumption is 1393 made to reduce the size of the Flooding Topology advertisement. 1395 6.6.2. Use of LANs in Distributed Mode 1397 In distributed mode, the flooding topology is NOT advertised, 1398 therefore the space consumed to advertise it is not a concern. It is 1399 therefore possible to assign only a subset of the nodes connected to 1400 the LAN to use the LAN as part of the flooding topology. Doing so 1401 may further optimize flooding by reducing the amount of redundant 1402 flooding on a LAN. However, support of flooding only by a subset of 1403 the nodes connected to a LAN requires some modest - but backwards 1404 compatible - changes in the way flooding is performed on a LAN. 1406 6.6.2.1. Partial flooding on a LAN in IS-IS 1408 Designated Intermediate System (DIS) for a LAN MUST use standard 1409 flooding behavior. 1411 Non-DIS nodes whose connection to the LAN is included in the flooding 1412 topology MUST use standard flooding behavior. 1414 Non-DIS nodes whose connection to the LAN is NOT included in the 1415 flooding topology behave as follows: 1417 o Received CSNPs from the DIS are ignored 1419 o PSNPs are NOT originated on the LAN 1421 o LSPs received on the LAN which are newer than the corresponding 1422 LSP present in the LSPDB are retained and flooded on all local 1423 circuits which are part of the flooding topology (i.e., do not 1424 discard newer LSPs simply because they were received on a LAN 1425 which the receiving node is not using for flooding) 1427 o LSPs received on the LAN which are older or same as the 1428 corresponding LSP present in the LSPDB are silently discarded 1430 o LSPs received on links other than the LAN are NOT flooded on the 1431 LAN 1433 NOTE: If any node connected to the LAN requests the enablement of 1434 temporary flooding all nodes revert to standard flooding behavior. 1436 6.6.2.2. Partial Flooding on a LAN in OSPF 1438 Designated Router (DR) and Backup Designated Router (BDR) for LANs 1439 MUST use standard flooding behavior. 1441 Non-DR/BDR nodes whose connection to the LAN is included in the 1442 flooding topology use standard flooding behavior. 1444 Non-DR/BDR nodes whose connection to the LAN is NOT included in the 1445 flooding topology behave as follows: 1447 o LSAs received on the LAN are acknowledged to DR/BDR 1449 o LSAs received on interfaces other than the LAN are NOT flooded on 1450 the LAN 1452 NOTE: If any node connected to the LAN requests the enablement of 1453 temporary flooding all nodes revert to standard flooding behavior. 1455 NOTE: The sending of LSA acks by nodes NOT using the LAN as part of 1456 the flooding topology eliminates the need for changes on the part of 1457 the DR/BDR - which might Include nodes which do not support the 1458 flooding optimizations. 1460 6.7. Flooding Behavior 1462 Nodes that support Dynamic Flooding MUST use the flooding topology 1463 for flooding when possible, and MUST NOT revert to standard flooding 1464 when a valid flooding topology is available. 1466 In some cases a node that supports Dynamic Flooding may need to add a 1467 local link(s) to the flooding topology temporarily, even though the 1468 link(s) is not part of the calculated flooding topology. This is 1469 termed "temporary flooding" and is discussed in Section 6.8.1. 1471 The flooding topology is calculated locally in the case of 1472 distributed mode. In centralized mode the flooding topology is 1473 advertised in the area link state database. Received link state 1474 updates, whether received on a link that is in the flooding topology 1475 or on a link that is not in the flooding topology, MUST be flooded on 1476 all links that are in the flooding topology, except for the link on 1477 which the update was received. 1479 In centralized mode, if multiple flooding topologies are present in 1480 the area link state database, the node SHOULD flood on each of these 1481 topologies. 1483 When the flooding topology changes on a node, either as a result of 1484 the local computation in distributed mode or as a result of the 1485 advertisement from the Area Leader in centralized mode, the node MUST 1486 continue to flood on both the old and new flooding topology for a 1487 limited amount of time. This is required to provide all nodes 1488 sufficient time to migrate to the new flooding topology. 1490 6.8. Treatment of Topology Events 1492 In this section, we explicitly consider a variety of different 1493 topological events in the network and how Dynamic Flooding should 1494 address them. 1496 6.8.1. Temporary Addition of Link to Flooding Topology 1498 In some cases a node that supports Dynamic Flooding may need to add a 1499 local link(s) to the flooding topology temporarily, even though the 1500 link(s) is not part of the calculated flooding topology. We refer to 1501 this as "temporary flooding" on the link. 1503 When temporary flooding is enabled on the link, the flooding needs to 1504 be enabled from both directions on the link. To achieve that, the 1505 following steps MUST be performed: 1507 Link State Database needs to be re-synchronised on the link. This 1508 is done using the standard protocol mechanisms. In the case of 1509 IS-IS, this results in setting SRM bit for all LSPs on the circuit 1510 and sending compete set of CSNPs on it. In OSPF, the mechanism 1511 specified in [RFC4811] is used. 1513 Flooding is enabled locally on the link. 1515 Flooding is requested from the neighbor using the mechanism 1516 specified in section Section 5.1.5 or Section 5.2.7. 1518 The request for temporary flooding is withdrawn on the link when all 1519 of the following conditions are met: 1521 Node itself is connected to the current flooding topology. 1523 Adjacent node is connected to the current flooding topology. 1525 Any change in the flooding topology MUST result in evaluation of the 1526 above conditions for any link on which the temporary flooding was 1527 enabled. 1529 Temporary flooding is stopped on the link when both adjacent nodes 1530 stop requesting temporary flooding on the link. 1532 6.8.2. Local Link Addition 1534 If a local link is added to the topology, the protocol will form a 1535 normal adjacency on the link and update the appropriate link state 1536 advertisements for the nodes on either end of the link. These link 1537 state updates will be flooded on the flooding topology. 1539 In centralized mode, the Area Leader, upon receiving these updates, 1540 may choose to retain the existing flooding topology or may choose to 1541 modify the flooding topology. If it elects to change the flooding 1542 topology, it will update the flooding topology in the link state 1543 database and flood it using the new flooding topology. 1545 In distributed mode, any change in the topology, including the link 1546 addition, MUST trigger the flooding topology recalculation. This is 1547 done to ensure that all nodes converge to the same flooding topology, 1548 regardless of the time of the calculation. 1550 Temporary flooding MUST be enabled on the newly added local link, if 1551 at least one of the following conditions are met: 1553 The node on which the local link was added is not connected to the 1554 current flooding topology. 1556 The new adjacent node is not connected to the current flooding 1557 topology. 1559 Note that in this case there is no need to perform a database 1560 synchronization as part of the enablement of the temporary flooding, 1561 because it has been part of the adjacency bring-up itself. 1563 If multiple local links are added to the topology before the flooding 1564 topology is updated, temporary flooding MUST be enabled on a subset 1565 of these links. 1567 6.8.3. Node Addition 1569 If a node is added to the topology, then at least one link is also 1570 added to the topology. Section 6.8.2 applies. 1572 A node which has a large number of neighbors is at risk for 1573 introducing a local flooding storm if all neighbors are brought up at 1574 once and temporary flooding is enabled on all links simultaneously. 1575 The most robust way to address this is to limit the rate of initial 1576 adjacency formation following bootup. This both reduces unnecessary 1577 redundant flooding as part of initial database synchronization and 1578 minimizes the need for temporary flooding as it allows time for the 1579 new node to be added to the flooding topology after only a small 1580 number of adjacencies have been formed. 1582 In the event a node elects to bring up a large number of adjacencies 1583 simultaneously, a significant amount of redundant flooding may be 1584 introduced as multiple neighbors of the new node enable temporary 1585 flooding to the new node which initially is not part of the flooding 1586 topology. 1588 6.8.4. Failures of Link Not on Flooding Topology 1590 If a link that is not part of the flooding topology fails, then the 1591 adjacent nodes will update their link state advertisements and flood 1592 them on the flooding topology. 1594 In centralized mode, the Area Leader, upon receiving these updates, 1595 may choose to retain the existing flooding topology or may choose to 1596 modify the flooding topology. If it elects to change the flooding 1597 topology, it will update the flooding topology in the link state 1598 database and flood it using the new flooding topology. 1600 In distributed mode, any change in the topology, including the 1601 failure of the link that is not part of the flooding topology MUST 1602 trigger the flooding topology recalculation. This is done to ensure 1603 that all nodes converge to the same flooding topology, regardless of 1604 the time of the calculation. 1606 6.8.5. Failures of Link On the Flooding Topology 1608 If there is a failure on the flooding topology, the adjacent nodes 1609 will update their link state advertisements and flood them. If the 1610 original flooding topology is bi-connected, the flooding topology 1611 should still be connected despite a single failure. 1613 If the failed local link represented the only connection to the 1614 flooding topology on the node where the link failed, the node MUST 1615 enable temporary flooding on a subset of its local links. This 1616 allows the node to send its updated link state advertisement(s) and 1617 also keep receiving link state updates from other nodes in the 1618 network before the new flooding topology is calculated and 1619 distributed (in the case of centralized mode). 1621 In centralized mode, the Area Leader will notice the change in the 1622 flooding topology, recompute the flooding topology, and flood it 1623 using the new flooding topology. 1625 In distributed mode, all nodes supporting dynamic flooding will 1626 notice the change in the topology and recompute the new flooding 1627 topology. 1629 6.8.6. Node Deletion 1631 If a node is deleted from the topology, then at least one link is 1632 also removed from the topology. Section 6.8.4 and Section 6.8.5 1633 apply. 1635 6.8.7. Local Link Addition to the Flooding Topology 1637 If the new flooding topology is received in the case of centralized 1638 mode, or calculated locally in the case of distributed mode and the 1639 local link on the node that was not part of the flooding topology has 1640 been added to the flooding topology, the node MUST: 1642 Re-synchronize the Link State Database over the link. This is 1643 done using the standard protocol mechanisms. In the case of IS- 1644 IS, this results in setting SRM bit for all LSPs on the circuit 1645 and sending a complete set of CSNPs. In OSPF, the mechanism 1646 specified in [RFC4811] is used. 1648 Make the link part of the flooding topology and start flooding 1649 over it 1651 6.8.8. Local Link Deletion from the Flooding Topology 1653 If the new flooding topology is received in the case of centralized 1654 mode, or calculated locally in the case of distributed mode and the 1655 local link on the node that was part of the flooding topology has 1656 been removed from the flooding topology, the node MUST remove the 1657 link from the flooding topology. 1659 The node MUST keep flooding on such link for a limited amount of time 1660 to allow other nodes to migrate to the new flooding topology. 1662 If the removed local link represented the only connection to the 1663 flooding topology on the node, the node MUST enable temporary 1664 flooding on a subset of its local links. This allows the node to 1665 send its updated link state advertisement(s) and also keep receiving 1666 link state updates from other nodes in the network before the new 1667 flooding topology is calculated and distributed (in the case of 1668 centralized mode). 1670 6.8.9. Treatment of Disconnected Adjacent Nodes 1672 Every time there is a change in the flooding topology a node MUST 1673 check if there are any adjacent nodes that are disconnected from the 1674 current flooding topology. Temporary flooding MUST be enabled 1675 towards a subset of the disconnected nodes. 1677 6.8.10. Failure of the Area Leader 1679 The failure of the Area Leader can be detected by observing that it 1680 is no longer reachable. In this case, the Area Leader election 1681 process is repeated and a new Area Leader is elected. 1683 In order to minimize disruption to Dynamic Flooding if the Area 1684 Leader becomes unreachable, the node which has the second highest 1685 priority for becoming Area Leader (including the system identifier/ 1686 Router-ID tie breaker if necessary) SHOULD advertise the same 1687 algorithm in its Area Leader Sub-TLV as the Area Leader and (in 1688 centralized mode) SHOULD advertise a flooding topology. This SHOULD 1689 be done even when the Area Leader is reachable. 1691 In centralized mode, the new Area Leader will compute a new flooding 1692 topology and flood it using the new flooding topology. To minimze 1693 disruption, the new flooding topology SHOULD have as much in common 1694 as possible with the old flooding topology. This will minimize the 1695 risk of over-flooding. 1697 In the distributed mode, the new flooding topology will be calculated 1698 on all nodes that support the algorithm that is advertised by the new 1699 Area Leader. Nodes that do not support the algorithm advertised by 1700 the new Area Leader will no longer participate in Dynamic Flooding 1701 and will revert to standard flooding. 1703 6.8.11. Recovery from Multiple Failures 1705 In the unlikely event of multiple failures on the flooding topology, 1706 it may become partitioned. The nodes that remain active on the edges 1707 of the flooding topology partitions will recognize this and will try 1708 to repair the flooding topology locally by enabling temporary 1709 flooding towards the nodes that they consider disconnected from the 1710 flooding topology until a new flooding topology becomes connected 1711 again. 1713 Nodes where local failure was detected update their own link state 1714 advertisements and flood them on the remainder of the flooding 1715 topology. 1717 In centralized mode, the Area Leader will notice the change in the 1718 flooding topology, recompute the flooding topology, and flood it 1719 using the new flooding topology. 1721 In distributed mode, all nodes that actively participate in Dynamic 1722 Flooding will compute the new flooding topology. 1724 Note that this is very different from the area partition because 1725 there is still a connected network graph between the nodes in the 1726 area. The area may remain connected and forwarding may still be 1727 effective. 1729 6.8.12. Rate Limiting Temporary Flooding 1731 As discussed in the previous sections, there are events which require 1732 the introduction of temporary flooding on edges which are not part of 1733 the current flooding topology. This can occur regardless of whether 1734 the area is operating in centralized mode or distributed mode. 1736 Nodes which decide to enable temporary flooding also have to decide 1737 whether to do so on a subset of the edges which are currently not 1738 part of the flooding topology or on all the edges which are currently 1739 not part of the flooding topology. Doing the former risks a longer 1740 convergence time as it is possible that the initial set of edges 1741 enabled does not fully repair the flooding topology. Doing the 1742 latter risks introducing a flooding storm which destablizes the 1743 network. 1745 It is recommended that a node implement rate limiting on the number 1746 of edges on which it chooses to enable temporary flooding. Initial 1747 values for the number of edges to enable and the rate at which 1748 additional edges may subsequently be enabled is left as an 1749 implementation decision. 1751 7. IANA Considerations 1753 7.1. IS-IS 1755 This document requests the following code points from the "sub-TLVs 1756 for TLV 242" registry (IS-IS Router CAPABILITY TLV). 1758 Type: TBD1 1760 Description: IS-IS Area Leader Sub-TLV 1762 Reference: This document (Section 5.1.1) 1764 Type: TBD7 1766 Description: IS-IS Dynamic Flooding Sub-TLV 1768 Reference: This document (Section 5.1.2) 1770 This document requests that IANA allocate and assign code points from 1771 the "IS-IS TLV Codepoints" registry. One for each of the following 1772 TLVs: 1774 Type: TBD2 1776 Description: IS-IS Area System IDs TLV 1778 Reference: This document (Section 5.1.3) 1780 Type: TBD3 1782 Description: IS-IS Flooding Path TLV 1784 Reference: This document (Section 5.1.4) 1786 Type: TBD9 1788 Description: IS-IS Flooding Request TLV 1790 Reference: This document (Section 5.1.5) 1792 This document requests that IANA allocate a new bit value from the 1793 "link-attribute bit values for sub-TLV 19 of TLV 22" registry. 1795 Local Edge Enabled for Flooding (LEEF) - suggested value 4 (to be 1796 assigned by IANA) 1798 7.2. OSPF 1800 This document requests the following code points from the "OSPF 1801 Router Information (RI) TLVs" registry: 1803 Type: TBD4 1805 Description: OSPF Area Leader Sub-TLV 1806 Reference: This document (Section 5.2.1) 1808 Type: TBD8 1810 Description: OSPF Dynamic Flooding Sub-TLV 1812 Reference: This document (Section 5.2.2) 1814 This document requests the following code point from the "Opaque 1815 Link-State Advertisements (LSA) Option Types" registry: 1817 Type: TBD5 1819 Description: OSPFv2 Dynamic Flooding Opaque LSA 1821 Reference: This document (Section 5.2.3) 1823 This document requests the following code point from the "OSPFv3 LSA 1824 Function Codes" registry: 1826 Type: TBD6 1828 Description: OSPFv3 Dynamic Flooding LSA 1830 Reference: This document (Section 5.2.4) 1832 This document requests a new bit in LLS Type 1 Extended Options and 1833 Flags registry: 1835 Bit Position: TBD10 1837 Description: Flooding Request bit 1839 Reference: This document (Section 5.2.7) 1841 This document requests the following code point from the "OSPFv2 1842 Extended Link TLV Sub-TLVs" registry: 1844 Type: TBD11 1846 Description: OSPFv2 Link Attributes Bits Sub-TLV 1848 Reference: This document (Section 5.2.8) 1850 This document requests the following code point from the "OSPFv3 1851 Extended LSA Sub-TLVs" registry: 1853 Type: TBD12 1854 Description: OSPFv3 Link Attributes Bits Sub-TLV 1856 Reference: This document (Section 5.2.8) 1858 7.2.1. OSPF Dynamic Flooding LSA TLVs Registry 1860 This specification also requests a new registry - "OSPF Dynamic 1861 Flooding LSA TLVs". New values can be allocated via IETF Review or 1862 IESG Approval 1864 The "OSPF Dynamic Flooding LSA TLVs" registry will define top-level 1865 TLVs for the OSPFv2 Dynamic Flooding Opaque LSA and OSPFv3 Dynamic 1866 Flooding LSAs. It should be added to the "Open Shortest Path First 1867 (OSPF) Parameters" registries group. 1869 The following initial values are allocated: 1871 Type: 0 1873 Description: Reserved 1875 Reference: This document 1877 Type: 1 1879 Description: OSPF Area Router IDs TLV 1881 Reference: This document (Section 5.2.5) 1883 Type: 2 1885 Description: OSPF Flooding Path TLV 1887 Reference: This document (Section 5.2.6) 1889 Types in the range 32768-33023 are for experimental use; these will 1890 not be registered with IANA, and MUST NOT be mentioned by RFCs. 1892 Types in the range 33024-65535 are not to be assigned at this time. 1893 Before any assignments can be made in the 33024-65535 range, there 1894 MUST be an IETF specification that specifies IANA Considerations that 1895 covers the range being assigned. 1897 7.2.2. OSPF Link Attributes Sub-TLV Bit Values Registry 1899 This specification also requests a new registry - "OSPF Link 1900 Attributes Sub-TLV Bit Values". New values can be allocated via IETF 1901 Review or IESG Approval 1902 The "OSPF Link Attributes Sub-TLV Bit Values" registry defines Link 1903 Attribute bit values for the OSPFv2 Link Attributes Sub-TLV and 1904 OSPFv3 Link Attributes Sub-TLV. It should be added to the "Open 1905 Shortest Path First (OSPF) Parameters" registries group. 1907 The following initial value is allocated: 1909 Bit Number: 0 1911 Description: Local Edge Enabled for Flooding(LEEF) 1913 Reference: This document (Section 5.2.8) 1915 7.3. IGP 1917 IANA is requested to set up a registry called "IGP Algorithm Type For 1918 Computing Flooding Topology" under an existing "Interior Gateway 1919 Protocol (IGP) Parameters" IANA registries. 1921 Values in this registry come from the range 0-255. 1923 The initial values in the IGP Algorithm Type For Computing Flooding 1924 Topology registry are: 1926 0: Reserved for centralized mode. Individual values are are to be 1927 assigned according to the "Specification Required" policy defined 1928 in [RFC8126] 1930 1-127: Available for standards action.Individual values are are to 1931 be assigned according to the "Private Use" policy defined in 1932 [RFC8126] 1934 128-254: Reserved for private use. 1936 255: Reserved. 1938 8. Security Considerations 1940 This document introduces no new security issues. Security of routing 1941 within a domain is already addressed as part of the routing protocols 1942 themselves. This document proposes no changes to those security 1943 architectures. 1945 It is possible that an attacker could become Area Leader and 1946 introduce a flawed flooding algorithm into the network thus 1947 compromising the operation of the protocol. Authentication methods 1948 as describe in [RFC5304] and [RFC5310] for IS-IS, [RFC2328] and 1950 [RFC7474] for OSPFv2 and [RFC5340] and [RFC4552] for OSPFv3 SHOULD be 1951 used to prevent such attack. 1953 9. Acknowledgements 1955 The authors would like to thank Sarah Chen for her contribution to 1956 this work. 1958 The authors would like to thank Zeqing (Fred) Xia, Naiming Shen, Adam 1959 Sweeney and Olufemi Komolafe for their helpful comments. 1961 The authors would like to thank Tom Edsall for initially introducing 1962 them to the problem. 1964 Advertising Local Edges Enabled for Flooding (LEEF) is based on an 1965 idea proposed in [I-D.cc-lsr-flooding-reduction]. We wish to thank 1966 the authors of that draft. 1968 10. References 1970 10.1. Normative References 1972 [ISO10589] 1973 International Organization for Standardization, 1974 "Intermediate System to Intermediate System Intra-Domain 1975 Routing Exchange Protocol for use in Conjunction with the 1976 Protocol for Providing the Connectionless-mode Network 1977 Service (ISO 8473)", ISO/IEC 10589:2002, Nov. 2002. 1979 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1980 Requirement Levels", BCP 14, RFC 2119, 1981 DOI 10.17487/RFC2119, March 1997, 1982 . 1984 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 1985 DOI 10.17487/RFC2328, April 1998, 1986 . 1988 [RFC4552] Gupta, M. and N. Melam, "Authentication/Confidentiality 1989 for OSPFv3", RFC 4552, DOI 10.17487/RFC4552, June 2006, 1990 . 1992 [RFC5029] Vasseur, JP. and S. Previdi, "Definition of an IS-IS Link 1993 Attribute Sub-TLV", RFC 5029, DOI 10.17487/RFC5029, 1994 September 2007, . 1996 [RFC5250] Berger, L., Bryskin, I., Zinin, A., and R. Coltun, "The 1997 OSPF Opaque LSA Option", RFC 5250, DOI 10.17487/RFC5250, 1998 July 2008, . 2000 [RFC5304] Li, T. and R. Atkinson, "IS-IS Cryptographic 2001 Authentication", RFC 5304, DOI 10.17487/RFC5304, October 2002 2008, . 2004 [RFC5310] Bhatia, M., Manral, V., Li, T., Atkinson, R., White, R., 2005 and M. Fanto, "IS-IS Generic Cryptographic 2006 Authentication", RFC 5310, DOI 10.17487/RFC5310, February 2007 2009, . 2009 [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF 2010 for IPv6", RFC 5340, DOI 10.17487/RFC5340, July 2008, 2011 . 2013 [RFC7356] Ginsberg, L., Previdi, S., and Y. Yang, "IS-IS Flooding 2014 Scope Link State PDUs (LSPs)", RFC 7356, 2015 DOI 10.17487/RFC7356, September 2014, 2016 . 2018 [RFC7474] Bhatia, M., Hartman, S., Zhang, D., and A. Lindem, Ed., 2019 "Security Extension for OSPFv2 When Using Manual Key 2020 Management", RFC 7474, DOI 10.17487/RFC7474, April 2015, 2021 . 2023 [RFC7684] Psenak, P., Gredler, H., Shakir, R., Henderickx, W., 2024 Tantsura, J., and A. Lindem, "OSPFv2 Prefix/Link Attribute 2025 Advertisement", RFC 7684, DOI 10.17487/RFC7684, November 2026 2015, . 2028 [RFC7770] Lindem, A., Ed., Shen, N., Vasseur, JP., Aggarwal, R., and 2029 S. Shaffer, "Extensions to OSPF for Advertising Optional 2030 Router Capabilities", RFC 7770, DOI 10.17487/RFC7770, 2031 February 2016, . 2033 [RFC7981] Ginsberg, L., Previdi, S., and M. Chen, "IS-IS Extensions 2034 for Advertising Router Information", RFC 7981, 2035 DOI 10.17487/RFC7981, October 2016, 2036 . 2038 [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for 2039 Writing an IANA Considerations Section in RFCs", BCP 26, 2040 RFC 8126, DOI 10.17487/RFC8126, June 2017, 2041 . 2043 [RFC8362] Lindem, A., Roy, A., Goethals, D., Reddy Vallem, V., and 2044 F. Baker, "OSPFv3 Link State Advertisement (LSA) 2045 Extensibility", RFC 8362, DOI 10.17487/RFC8362, April 2046 2018, . 2048 10.2. Informative References 2050 [Clos] Clos, C., "A Study of Non-Blocking Switching Networks", 2051 The Bell System Technical Journal Vol. 32(2), DOI 2052 10.1002/j.1538-7305.1953.tb01433.x, March 1953, 2053 . 2055 [I-D.cc-lsr-flooding-reduction] 2056 Chen, H., Cheng, D., Toy, M., Yang, Y., Wang, A., Liu, X., 2057 Fan, Y., and L. Liu, "Flooding Topology Computation 2058 Algorithm", draft-cc-lsr-flooding-reduction-08 (work in 2059 progress), March 2020. 2061 [Leiserson] 2062 Leiserson, C., "Fat-Trees: Universal Networks for 2063 Hardware-Efficient Supercomputing", IEEE Transactions on 2064 Computers 34(10):892-901, 1985. 2066 [RFC2973] Balay, R., Katz, D., and J. Parker, "IS-IS Mesh Groups", 2067 RFC 2973, DOI 10.17487/RFC2973, October 2000, 2068 . 2070 [RFC3630] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering 2071 (TE) Extensions to OSPF Version 2", RFC 3630, 2072 DOI 10.17487/RFC3630, September 2003, 2073 . 2075 [RFC4811] Nguyen, L., Roy, A., and A. Zinin, "OSPF Out-of-Band Link 2076 State Database (LSDB) Resynchronization", RFC 4811, 2077 DOI 10.17487/RFC4811, March 2007, 2078 . 2080 [RFC7938] Lapukhov, P., Premji, A., and J. Mitchell, Ed., "Use of 2081 BGP for Routing in Large-Scale Data Centers", RFC 7938, 2082 DOI 10.17487/RFC7938, August 2016, 2083 . 2085 Authors' Addresses 2086 Tony Li (editor) 2087 Arista Networks 2088 5453 Great America Parkway 2089 Santa Clara, California 95054 2090 USA 2092 Email: tony.li@tony.li 2094 Peter Psenak (editor) 2095 Cisco Systems, Inc. 2096 Eurovea Centre, Central 3 2097 Pribinova Street 10 2098 Bratislava 81109 2099 Slovakia 2101 Email: ppsenak@cisco.com 2103 Les Ginsberg 2104 Cisco Systems, Inc. 2105 510 McCarthy Blvd. 2106 Milpitas, California 95035 2107 USA 2109 Email: ginsberg@cisco.com 2111 Huaimo Chen 2112 Futurewei 2113 Boston, Ma 2114 USA 2116 Email: hchen@futurewei.com 2118 Tony Przygienda 2119 Juniper Networks, Inc. 2120 1194 N. Mathilda Ave 2121 Sunnyvale, California 94089 2122 USA 2124 Email: prz@juniper.net 2125 Dave Cooper 2126 CenturyLink 2127 1025 Eldorado Blvd 2128 Broomfield, Colorado 80021 2129 USA 2131 Email: Dave.Cooper@centurylink.com 2133 Luay Jalil 2134 Verizon 2135 Richardson, Texas 75081 2136 USA 2138 Email: luay.jalil@verizon.com 2140 Srinath Dontula 2141 ATT 2142 200 S Laurel Ave 2143 Middletown, New Jersey 07748 2144 USA 2146 Email: sd947e@att.com