idnits 2.17.00 (12 Aug 2021) /tmp/idnits13346/draft-ietf-lsr-dynamic-flooding-01.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 21, 2019) is 1096 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) == Unused Reference: 'RFC5613' is defined on line 1976, but no explicit reference was found in the text == Unused Reference: 'RFC7120' is defined on line 1981, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'ISO10589' == Outdated reference: A later version (-09) exists of draft-cc-lsr-flooding-reduction-03 Summary: 0 errors (**), 0 flaws (~~), 4 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 22, 2019 L. Ginsberg 6 Cisco Systems, Inc. 7 T. Przygienda 8 Juniper Networks, Inc. 9 D. Cooper 10 CenturyLink 11 L. Jalil 12 Verizon 13 S. Dontula 14 ATT 15 May 21, 2019 17 Dynamic Flooding on Dense Graphs 18 draft-ietf-lsr-dynamic-flooding-01 20 Abstract 22 Routing with link state protocols in dense network topologies can 23 result in sub-optimal convergence times due to the overhead 24 associated with flooding. This can be addressed by decreasing the 25 flooding topology so that it is less dense. 27 This document discusses the problem in some depth and an 28 architectural solution. Specific protocol changes for IS-IS, OSPFv2, 29 and OSPFv3 are described in this document. 31 Status of This Memo 33 This Internet-Draft is submitted in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF). Note that other groups may also distribute 38 working documents as Internet-Drafts. The list of current Internet- 39 Drafts is at https://datatracker.ietf.org/drafts/current/. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 This Internet-Draft will expire on November 22, 2019. 48 Copyright Notice 50 Copyright (c) 2019 IETF Trust and the persons identified as the 51 document authors. All rights reserved. 53 This document is subject to BCP 78 and the IETF Trust's Legal 54 Provisions Relating to IETF Documents 55 (https://trustee.ietf.org/license-info) in effect on the date of 56 publication of this document. Please review these documents 57 carefully, as they describe your rights and restrictions with respect 58 to this document. Code Components extracted from this document must 59 include Simplified BSD License text as described in Section 4.e of 60 the Trust Legal Provisions and are provided without warranty as 61 described in the Simplified BSD License. 63 Table of Contents 65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 66 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 5 67 2. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 5 68 3. Solution Requirements . . . . . . . . . . . . . . . . . . . . 5 69 4. Dynamic Flooding . . . . . . . . . . . . . . . . . . . . . . 6 70 4.1. Applicability . . . . . . . . . . . . . . . . . . . . . . 7 71 4.2. Leader election . . . . . . . . . . . . . . . . . . . . . 8 72 4.3. Computing the Flooding Topology . . . . . . . . . . . . . 8 73 4.4. Topologies on Complete Bipartite Graphs . . . . . . . . . 9 74 4.4.1. A Minimal Flooding Topology . . . . . . . . . . . . . 9 75 4.4.2. Xia Topologies . . . . . . . . . . . . . . . . . . . 10 76 4.4.3. Optimization . . . . . . . . . . . . . . . . . . . . 11 77 4.5. Encoding the Flooding Topology . . . . . . . . . . . . . 11 78 4.6. Advertising the Local Edges Enabled for Flooding . . . . 11 79 5. Protocol Elements . . . . . . . . . . . . . . . . . . . . . . 12 80 5.1. IS-IS TLVs . . . . . . . . . . . . . . . . . . . . . . . 12 81 5.1.1. IS-IS Area Leader Sub-TLV . . . . . . . . . . . . . . 12 82 5.1.2. IS-IS Dynamic Flooding Sub-TLV . . . . . . . . . . . 13 83 5.1.3. IS-IS Area Node IDs TLV . . . . . . . . . . . . . . . 14 84 5.1.4. IS-IS Flooding Path TLV . . . . . . . . . . . . . . . 15 85 5.1.5. IS-IS Flooding Request TLV . . . . . . . . . . . . . 16 86 5.1.6. IS-IS LEEF Advertisement . . . . . . . . . . . . . . 18 87 5.2. OSPF LSAs and TLVs . . . . . . . . . . . . . . . . . . . 18 88 5.2.1. OSPF Area Leader Sub-TLV . . . . . . . . . . . . . . 18 89 5.2.2. OSPF Dynamic Flooding Sub-TLV . . . . . . . . . . . . 19 90 5.2.3. OSPFv2 Dynamic Flooding Opaque LSA . . . . . . . . . 19 91 5.2.4. OSPFv3 Dynamic Flooding LSA . . . . . . . . . . . . . 21 92 5.2.5. OSPF Area Router ID TLVs . . . . . . . . . . . . . . 22 93 5.2.5.1. OSPFv2 Area Router ID TLV . . . . . . . . . . . . 22 94 5.2.5.2. OSPFv3 Area Router ID TLV . . . . . . . . . . . . 24 95 5.2.6. OSPF Flooding Path TLV . . . . . . . . . . . . . . . 26 96 5.2.7. OSPF Flooding Request Bit . . . . . . . . . . . . . . 27 97 5.2.8. OSPF LEEF Advertisement . . . . . . . . . . . . . . . 28 98 6. Behavioral Specification . . . . . . . . . . . . . . . . . . 28 99 6.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 29 100 6.2. Flooding Topology . . . . . . . . . . . . . . . . . . . . 29 101 6.3. Leader Election . . . . . . . . . . . . . . . . . . . . . 29 102 6.4. Area Leader Responsibilities . . . . . . . . . . . . . . 30 103 6.5. Distributed Flooding Topology Calculation . . . . . . . . 30 104 6.6. Use of LANs in the Flooding Topology . . . . . . . . . . 30 105 6.6.1. Use of LANs in Centralized mode . . . . . . . . . . . 30 106 6.6.2. Use of LANs in Distributed Mode . . . . . . . . . . . 31 107 6.6.2.1. Partial flooding on a LAN in IS-IS . . . . . . . 31 108 6.6.2.2. Partial Flooding on a LAN in OSPF . . . . . . . . 31 109 6.7. Flooding Behavior . . . . . . . . . . . . . . . . . . . . 32 110 6.8. Treatment of Topology Events . . . . . . . . . . . . . . 33 111 6.8.1. Temporary Addition of Link to Flooding Topology . . . 33 112 6.8.2. Local Link Addition . . . . . . . . . . . . . . . . . 33 113 6.8.3. Node Addition . . . . . . . . . . . . . . . . . . . . 34 114 6.8.4. Failures of Link Not on Flooding Topology . . . . . . 35 115 6.8.5. Failures of Link On the Flooding Topology . . . . . . 35 116 6.8.6. Node Deletion . . . . . . . . . . . . . . . . . . . . 35 117 6.8.7. Local Link Addition to the Flooding Topology . . . . 36 118 6.8.8. Local Link Deletion from the Flooding Topology . . . 36 119 6.8.9. Treatment of Disconnected Adjacent Nodes . . . . . . 36 120 6.8.10. Failure of the Area Leader . . . . . . . . . . . . . 36 121 6.8.11. Recovery from Multiple Failures . . . . . . . . . . . 37 122 6.8.12. Rate Limiting Temporary Flooding . . . . . . . . . . 37 123 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 38 124 7.1. IS-IS . . . . . . . . . . . . . . . . . . . . . . . . . . 38 125 7.2. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . 39 126 7.2.1. OSPF Dynamic Flooding LSA TLVs Registry . . . . . . . 40 127 7.2.2. OSPF Link Attributes Sub-TLV Bit Values Registry . . 41 128 7.3. IGP . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 129 8. Security Considerations . . . . . . . . . . . . . . . . . . . 42 130 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 42 131 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 42 132 10.1. Normative References . . . . . . . . . . . . . . . . . . 42 133 10.2. Informative References . . . . . . . . . . . . . . . . . 44 134 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 45 136 1. Introduction 138 In recent years, there has been increased focus on how to address the 139 dynamic routing of networks that have a bipartite (a.k.a. spine-leaf 140 or leaf-spine), Clos [Clos], or Fat Tree [Leiserson] topology. 141 Conventional Interior Gateway Protocols (IGPs, i.e., IS-IS 142 [ISO10589], OSPFv2 [RFC2328], and OSPFv3 [RFC5340]) under-perform, 143 redundantly flooding information throughout the dense topology, 144 leading to overloaded control plane inputs and thereby creating 145 operational issues. For practical considerations, network architects 146 have resorted to applying unconventional techniques to address the 147 problem, e.g., applying BGP in the data center [RFC7938]. However it 148 is very clear that using an Exterior Gateway Protocol as an IGP is 149 sub-optimal, if only due to the configuration overhead. 151 The primary issue that is demonstrated when conventional mechanisms 152 are applied is the poor reaction of the network to topology changes. 153 Normal link state routing protocols rely on a flooding algorithm for 154 state distribution within an area. In a dense topology, this 155 flooding algorithm is highly redundant, resulting in unnecessary 156 overhead. Each node in the topology receives each link state update 157 multiple times. Ultimately, all of the redundant copies will be 158 discarded, but only after they have reached the control plane and 159 been processed. This creates issues because significant link state 160 database updates can become queued behind many redundant copies of 161 another update. This delays convergence as the link state database 162 does not stabilize promptly. 164 In a real world implementation, the packet queues leading to the 165 control plane are necessarily of finite size, so if the flooding rate 166 exceeds the update processing rate for long enough, the control plane 167 will be obligated to drop incoming updates. If these lost updates 168 are of significance, this will further delay stabilization of the 169 link state database and the convergence of the network. 171 This is not a new problem. Historically, when routing protocols have 172 been deployed in networks where the underlying topology is a complete 173 graph, there have been similar issues. This was more common when the 174 underlying link layer fabric presented the network layer with a full 175 mesh of virtual connections. This was addressed by reducing the 176 flooding topology through IS-IS Mesh Groups [RFC2973], but this 177 approach requires careful configuration of the flooding topology. 179 Thus, the root problem is not limited to massively scalable data 180 centers. It exists with any dense topology at scale. 182 This problem is not entirely surprising. Link state routing 183 protocols were conceived when links were very expensive and 184 topologies were sparse. The fact that those same designs are sub- 185 optimal in a dense topology should not come as a huge surprise. The 186 fundamental premise that was addressed by the original designs was an 187 environment of extreme cost and scarcity. Technology has progressed 188 to the point where links are cheap and common. This represents a 189 complete reversal in the economic fundamentals of network 190 engineering. The original designs are to be commended for continuing 191 to provide correct operation to this point, and optimizations for 192 operation in today's environment are to be expected. 194 1.1. Requirements Language 196 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 197 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 198 document are to be interpreted as described in RFC 2119 [RFC2119]. 200 2. Problem Statement 202 In a dense topology, the flooding algorithm that is the heart of 203 conventional link state routing protocols causes a great deal of 204 redundant messaging. This is exacerbated by scale. While the 205 protocol can survive this combination, the redundant messaging is 206 unnecessary overhead and delays convergence. Thus, the problem is to 207 provide routing in dense, scalable topologies with rapid convergence. 209 3. Solution Requirements 211 A solution to this problem must then meet the following requirements: 213 Requirement 1 Provide a dynamic routing solution. Reachability 214 must be restored after any topology change. 216 Requirement 2 Provide a significant improvement in convergence. 218 Requirement 3 The solution should address a variety of dense 219 topologies. Just addressing a complete bipartite topology such 220 as K5,8 is insufficient. Multi-stage Clos topologies must also 221 be addressed, as well as topologies that are slight variants. 222 Addressing complete graphs is a good demonstration of generality. 224 Requirement 4 There must be no single point of failure. The loss 225 of any link or node should not unduly hinder convergence. 227 Requirement 5 Dense topologies are subgraphs of much larger 228 topologies. Operational efficiency requires that the dense 229 subgraph not operate in a radically different manner than the 230 remainder of the topology. While some operational differences 231 are permissible, they should be minimized. Changes to nodes 232 outside of the dense subgraph are not acceptable. These 233 situations occur when massively scaled data centers are part of 234 an overall larger wide-area network. Having a second protocol 235 operating just on this subgraph would add much more complexity at 236 the edge of the subgraph where the two protocols would have to 237 inter-operate. 239 4. Dynamic Flooding 241 We have observed that the combination of the dense topology and 242 flooding on the physical topology in a scalable network is sub- 243 optimal. However, if we decouple the flooding topology from the 244 physical topology and only flood on a greatly reduced portion of that 245 topology, we can have efficient flooding and retain all of the 246 resilience of existing protocols. A node that supports flooding on 247 the decoupled flooding topology is said to support dynamic flooding. 249 In this idea, the flooding topology is computed within an IGP area 250 with the dense topology either centrally on an elected node, termed 251 the Area Leader, or in a distributed manner on all nodes that are 252 supporting Dynamic Flooding. If the flooding topology is computed 253 centrally, it is encoded into and distributed as part of the normal 254 link state database. We call this the centralized mode of operation. 255 If the flooding topology is computed in a distributed fashion, we 256 call this the distributed mode of operation. Nodes within such an 257 IGP area would only flood on the flooding topology. On links outside 258 of the normal flooding topology, normal database synchronization 259 mechanisms (i.e., OSPF database exchange, IS-IS CSNPs) would apply, 260 but flooding may not. Details are described in Section 6. New link 261 state information that arrives from outside of the flooding topology 262 suggests that the sender has a different or no flooding topology 263 information and that the link state update should be flooded on the 264 flooding topology as well. 266 The flooding topology covers the full set of nodes within the area, 267 but excludes some of the links that standard flooding would employ. 269 Since the flooding topology is computed prior to topology changes, it 270 does not factor into the convergence time and can be done when the 271 topology is stable. The speed of the computation and its 272 distribution, in the case of a centralized mode, is not a significant 273 issue. 275 If a node does not have any flooding topology information when it 276 receives new link state information, it should flood according to 277 standard flooding rules. This situation will occur when the dense 278 topology is first established, but is unlikely to recur. 280 When centralized mode is used and if, during a transient, there are 281 multiple flooding topologies being advertised, then nodes should 282 flood link state updates on all of the flooding topologies. Each 283 node should locally evaluate the election of the Area Leader for the 284 IGP area and first flood on its flooding topology. The rationale 285 behind this is straightforward: if there is a transient and there has 286 been a recent change in Area Leader, then propagating topology 287 information promptly along the most likely flooding topology should 288 be the priority. 290 During transients, it is possible that loops will form in the 291 flooding topology. This is not problematic, as the legacy flooding 292 rules would cause duplicate updates to be ignored. Similarly, during 293 transients, it is possible that the flooding topology may become 294 disconnected. Section 6.8.11 discusses how such conditions are 295 handled. 297 4.1. Applicability 299 In a complete graph, this approach is appealing because it 300 drastically decreases the flooding topology without the manual 301 configuration of mesh groups. By controlling the diameter of the 302 flooding topology, as well as the maximum degree node in the flooding 303 topology, convergence time goals can be met and the stability of the 304 control plane can be assured. 306 Similarly, in a massively scaled data center, where there are many 307 opportunities for redundant flooding, this mechanism ensures that 308 flooding is redundant, with each leaf and spine well connected, while 309 ensuring that no update need make too many hops and that no node 310 shares an undue portion of the flooding effort. 312 In a network where only a portion of the nodes support Dynamic 313 Flooding, the remaining nodes will continue to perform standard 314 flooding. This is not an issue for correctness, as no node can 315 become isolated. 317 Flooding that is initiated by nodes that support Dynamic Flooding 318 will remain within the flooding topology until it reaches a legacy 319 node, which will resume legacy flooding. Standard flooding will be 320 bounded by nodes supporting Dynamic Flooding, which can help limit 321 the propagation of unnecessary flooding. Whether or not the network 322 can remain stable in this condition is unknown and may be very 323 dependent on the number and location of the nodes that support 324 Dynamic Flooding. 326 During incremental deployment of dynamic flooding an area will 327 consist of one or more sets of connected nodes that support dynamic 328 flooding and one or more sets of connected nodes that do not, i.e., 329 nodes that support standard flooding. The flooding topology is the 330 union of these sets of nodes. Each set of nodes that does not 331 support dynamic flooding needs to be part of the flooding topology 332 and such a set of nodes may provide connectivity between two or more 333 sets of nodes that support dynamic flooding. 335 4.2. Leader election 337 A single node within the dense topology is elected as an Area Leader. 339 A generalization of the mechanisms used in existing Designated Router 340 (OSPF) or Designated Intermediate-System (IS-IS) elections suffices. 341 The elected node is known as the Area Leader. 343 In the case of centralized mode, the Area Leader is responsible for 344 computing and distributing the flooding topology. When a new Area 345 Leader is elected and has distributed new flooding topology 346 information, then any prior Area Leaders should withdraw any of their 347 flooding topology information from their link state database entries. 349 In the case of distributed mode, the distributed algorithm advertised 350 by the Area Leader MUST be used by all nodes that participate in 351 Dynamic Flooding. 353 Not every node needs to be a candidate to be Area Leader within an 354 area, as a single candidate is sufficient for correct operation. For 355 redundancy, however, it is strongly RECOMMENDED that there be 356 multiple candidates. 358 4.3. Computing the Flooding Topology 360 There is a great deal of flexibility in how the flooding topology may 361 be computed. For resilience, it needs to at least contain a cycle of 362 all nodes in the dense subgraph. However, additional links could be 363 added to decrease the convergence time. The trade-off between the 364 density of the flooding topology and the convergence time is a matter 365 for further study. The exact algorithm for computing the flooding 366 topology in the case of the centralized computation need not be 367 standardized, as it is not an interoperability issue. Only the 368 encoding of the result needs to be documented. In the case of 369 distributed mode, all nodes in the IGP area need to use the same 370 algorithm to compute the flooding topology. It is possible to use 371 private algorithms to compute flooding topology, so long as all nodes 372 in the IGP area use the same algorithm. 374 While the flooding topology should be a covering cycle, it need not 375 be a Hamiltonian cycle where each node appears only once. In fact, 376 in many relevant topologies this will not be possible e.g., K5,8. 377 This is fortunate, as computing a Hamiltonian cycle is known to be 378 NP-complete. 380 A simple algorithm to compute the topology for a complete bipartite 381 graph is to simply select unvisited nodes on each side of the graph 382 until both sides are completely visited. If the number of nodes on 383 each side of the graph are unequal, then revisiting nodes on the less 384 populated side of the graph will be inevitable. This algorithm can 385 run in O(N) time, so is quite efficient. 387 While a simple cycle is adequate for correctness and resiliency, it 388 may not be optimal for convergence. At scale, a cycle may have a 389 diameter that is half the number of nodes in the graph. This could 390 cause an undue delay in link state update propagation. Therefore it 391 may be useful to have a bound on the diameter of the flooding 392 topology. Introducing more links into the flooding topology would 393 reduce the diameter, but at the trade-off of possibly adding 394 redundant messaging. The optimal trade-off between convergence time 395 and graph diameter is for further study. 397 Similarly, if additional redundancy is added to the flooding 398 topology, specific nodes in that topology may end up with a very high 399 degree. This could result in overloading the control plane of those 400 nodes, resulting in poor convergence. Thus, it may be optimal to 401 have an upper bound on the degree of nodes in the flooding topology. 402 Again, the optimal trade-off between graph diameter, node degree, and 403 convergence time, and topology computation time is for further study. 405 If the leader chooses to include a multi-node broadcast LAN segment 406 as part of the flooding topology, all of the connectivity to that LAN 407 segment should be included as well. Once updates are flooded onto 408 the LAN, they will be received by every attached node. 410 4.4. Topologies on Complete Bipartite Graphs 412 Complete bipartite graph topologies have become popular for data 413 center applications and are commonly called leaf-spine or spine-leaf 414 topologies. In this section, we discuss some flooding topologies 415 that are of particular interest in these networks. 417 4.4.1. A Minimal Flooding Topology 419 We define a Minimal Flooding Topology on a complete bipartite graph 420 as one in which the topology is connected and each node has at least 421 degree two. This is of interest because it guarantees that the 422 flooding topology has no single points of failure. 424 In practice, this implies that every leaf node in the flooding 425 topology will have a degree of two. As there are usually more leaves 426 than spines, the degree of the spines will be higher, but the load on 427 the individual spines can be evenly distributed. 429 This type of flooding topology is also of interest because it scales 430 well. As the number of leaves increases, we can construct flooding 431 topologies that perform well. Specifically, for n spines and m 432 leaves, if m >= n(n/2-1), then there is a flooding topology that has 433 a diameter of four. 435 4.4.2. Xia Topologies 437 We define a Xia Topology on a complete bipartite graph as one in 438 which all spine nodes are bi-connected through leaves with degree 439 two, but the remaining leaves all have degree one and are evenly 440 distributed across the spines. 442 Constructively, we can create a Xia topology by iterating through the 443 spines. Each spine can be connected to the next spine by selecting 444 any unused leaf. Since leaves are connected to all spines, all 445 leaves will have a connection to both the first and second spine and 446 we can therefore choose any leaf without loss of generality. 447 Continuing this iteration across all of the spines, selecting a new 448 leaf at each iteration, will result in a path that connects all 449 spines. Adding one more leaf between the last and first spine will 450 produce a cycle of n spines and n leaves. 452 At this point, m-n leaves remain unconnected. These can be 453 distributed evenly across the remaining spines, connected by a single 454 link. 456 Xia topologies represent a compromise that trades off increased risk 457 and decreased performance for lower flooding amplification. Xia 458 topologies will have a larger diameter. For m spines, the diameter 459 will be m + 2. 461 In a Xia topology, some leaves are singly connected. This represents 462 a risk in that in some failures, convergence may be delayed. 463 However, there may be some alternate behaviors that can be employed 464 to mitigate these risks. If a leaf node sees that its single link on 465 the flooding topology has failed, it can compensate by performing a 466 database synchronization check with a different spine. Similarly, if 467 a leaf determines that its connected spine on the flooding topology 468 has failed, it can compensate by performing a database 469 synchronization check with a different spine. In both of these 470 cases, the synchronization check is intended to ameliorate any delays 471 in link state propagation due to the fragmentation of the flooding 472 topology. 474 The benefit of this topology is that flooding load is easily 475 understood. Each node in the spine cycle will never receive an 476 update more than twice. For m leaves and n spines, a spine never 477 transmits more than (m/n +1) updates. 479 4.4.3. Optimization 481 If two nodes are adjacent on the flooding topology and there are a 482 set of parallel links between them, then any given update MUST be 483 flooded over a single one of those links. Selection of the specific 484 link is implementation specific. 486 4.5. Encoding the Flooding Topology 488 There are a variety of ways that the flooding topology could be 489 encoded efficiently. If the topology was only a cycle, a simple list 490 of the nodes in the topology would suffice. However, this is 491 insufficiently flexible as it would require a slightly different 492 encoding scheme as soon as a single additional link is added. 493 Instead, we choose to encode the flooding topology as a set of 494 intersecting paths, where each path is a set of connected edges. 496 Advertisement of the flooding topology includes support for multi- 497 access LANs. When a LAN is included in the flooding topology, all 498 edges between the LAN and nodes connected to the LAN are assumed to 499 be part of the flooding topology. In order to reduce the size of the 500 flooding topology advertisement, explicit advertisement of these 501 edges is optional. Note that this may result in the possibility of 502 "hidden nodes" existing which are actually part of the flooding 503 topology but which are not explicitly mentioned in the flooding 504 topology advertisements. These hidden nodes can be found by 505 examination of the Link State database where connectivity between a 506 LAN and nodes connected to the LAN is fully specified. 508 Note that while all nodes MUST be part of the advertised flooding 509 topology not all multi-access LANs need to be included. Only those 510 LANs which are part of the flooding topology need to be included in 511 the advertised flooding topology. 513 Other encodings are certainly possible. We have attempted to make a 514 useful trade off between simplicity, generality, and space. 516 4.6. Advertising the Local Edges Enabled for Flooding 518 Correct operation of the flooding topology requires that all nodes 519 which participate in the flooding topology choose local links for 520 flooding which are consistent with the calculated flooding topology. 521 Failure to do so could result in unexpected partition of the flooding 522 topology and/or sub-optimal flooding reduction. As an aid to 523 diagnosing problems when dynamic flooding is in use, this document 524 defines a means of advertising what local edges are enabled for 525 flooding (LEEF). The protocol specific encodings are defined in 526 Sections 5.1.6 and 5.2.8. 528 The following guidelines apply: 530 Advertisement of LEEFs is optional. 532 As the flooding topology is defined by edges (not by links), in 533 cases where parallel adjacencies to the same neighbor exist, the 534 advertisement SHOULD indicate that all such links have been 535 enabled. 537 LEEF advertisements MUST NOT include edges enabled for temporary 538 flooding (Section 6.7). 540 LEEF advertisements MUST NOT be used either when calculating a 541 flooding topology or when determining what links to add 542 temporarily to the flooding topology when the flooding topology is 543 temporarily partitioned. 545 5. Protocol Elements 547 5.1. IS-IS TLVs 549 The following TLVs/sub-TLVs are added to IS-IS: 551 1. A sub-TLV that an IS may inject into its LSP to indicate its 552 preference for becoming Area Leader. 554 2. A sub-TLV that an IS may inject into its LSP to indicate that it 555 supports Dynamic Flooding and the algorithms that it supports for 556 distributed mode, if any. 558 3. A TLV to carry the list of system IDs that compromise the 559 flooding topology for the area. 561 4. A TLV to carry a path which is part of the flooding topology 563 5. A TLV that requests flooding from the adjacent node 565 5.1.1. IS-IS Area Leader Sub-TLV 567 The Area Leader Sub-TLV allows a system to: 569 1. Indicate its eligibility and priority for becoming Area Leader. 571 2. Indicate whether centralized or distributed mode is to be used to 572 compute the flooding topology in the area. 574 3. Indicate the algorithm identifier for the algorithm that is used 575 to compute the flooding topology in distributed mode. 577 Intermediate Systems (nodes) that are not advertising this Sub-TLV 578 are not eligible to become Area Leader. 580 The Area Leader is the node with the numerically highest Area Leader 581 priority in the area. In the event of ties, the node with the 582 numerically highest system ID is the Area Leader. Due to transients 583 during database flooding, different nodes may not agree on the Area 584 Leader. 586 The Area Leader Sub-TLV is advertised as a Sub-TLV of the IS-IS 587 Router Capability TLV-242 that is defined in [RFC7981] and has the 588 following format: 590 0 1 2 3 591 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 592 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 593 | Type | Length | Priority | Algorithm | 594 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 596 Type: TBD1 598 Length: 2 600 Priority: 0-255, unsigned integer 602 Algorithm: a numeric identifier in the range 0-255 that identifies 603 the algorithm used to calculate the flooding topology. The 604 following values are defined: 606 0: Centralized computation by the Area Leader. 608 1-127: Standardized distributed algorithms. Individual values 609 are are to be assigned according to the "Specification 610 Required" policy defined in [RFC8126] (see Section 7.3). 612 128-254: Private distributed algorithms. Individual values are 613 are to be assigned according to the "Private Use" policy 614 defined in [RFC8126] (see Section 7.3). 616 255: Reserved 618 5.1.2. IS-IS Dynamic Flooding Sub-TLV 620 The Dynamic Flooding Sub-TLV allows a system to: 622 1. Indicate that it supports Dynamic Flooding. This is indicated by 623 the advertisement of this Sub-TLV. 625 2. Indicate the set of algorithms that it supports for distributed 626 mode, if any. 628 In incremental deployments, understanding which nodes support Dynamic 629 Flooding can be used to optimize the flooding topology. In 630 distributed mode, knowing the capabilities of the nodes can allow the 631 Area Leader to select the optimal algorithm. 633 The Dynamic Flooding Sub-TLV is advertised as a Sub-TLV of the IS-IS 634 Router Capability TLV (242) [RFC7981] and has the following format: 636 0 1 2 3 637 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 638 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 639 | Type | Length | Algorithm... | 640 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 642 Type: TBD7 644 Length: 0-255; number of Algorithms 646 Algorithm: zero or more numeric identifiers in the range 0-255 647 that identifies the algorithm used to calculate the flooding 648 topology, as described in Section 5.1.1. 650 5.1.3. IS-IS Area Node IDs TLV 652 The IS-IS Area Node IDs TLV is only used in centralized mode. 654 The Area Node IDs TLV is used by the Area Leader to enumerate the 655 Node IDs (System ID + pseudo-node ID) that it has used in computing 656 the area flooding topology. Conceptually, the Area Leader creates a 657 list of node IDs for all nodes in the area (including pseudo-nodes 658 for all LANs in the topology), assigning indices to each node, 659 starting with index 0. 661 Because the space in a single TLV is limited, more than one TLV may 662 be required to encode all of the node IDs in the area. This TLV may 663 be present in multiple LSPs. 665 The format of the Area Node IDs TLV is: 667 0 1 2 3 668 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 669 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 670 | Type | Length | Starting Index | 671 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 672 |L| Reserved | Node IDs ... 673 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 674 Node IDs continued .... 675 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 677 Type: TBD2 679 Length: 3 + ((System ID Length + 1) * (number of node IDs)) 681 Starting index: The index of the first node ID that appears in 682 this TLV. 684 L (Last): This bit is set if the index of the last node ID that 685 appears in this TLV is equal to the last index in the full list of 686 node IDs for the area. 688 Node IDs: A concatenated list of node IDs for the area 690 If there are multiple IS-IS Area Node IDs TLVs with the L bit set 691 advertised by the same node, the TLV which specifies the smaller 692 maximum index is used and the other TLV(s) with L bit set are 693 ignored. TLVs which specify node IDs with indices greater than that 694 specified by the TLV with the L bit set are also ignored. 696 5.1.4. IS-IS Flooding Path TLV 698 IS-IS Flooding Path TLV is only used in centralized mode. 700 The Flooding Path TLV is used to denote a path in the flooding 701 topology. The goal is an efficient encoding of the links of the 702 topology. A single link is a simple case of a path that only covers 703 two nodes. A connected path may be described as a sequence of 704 indices: (I1, I2, I3, ...), denoting a link from the system with 705 index 1 to the system with index 2, a link from the system with index 706 2 to the system with index 3, and so on. 708 If a path exceeds the size that can be stored in a single TLV, then 709 the path may be distributed across multiple TLVs by the replication 710 of a single system index. 712 Complex topologies that are not a single path can be described using 713 multiple TLVs. 715 The Flooding Path TLV contains a list of system indices relative to 716 the systems advertised through the Area Node IDs TLV. At least 2 717 indices must be included in the TLV. Due to the length restriction 718 of TLVs, this TLV can contain at most 126 system indices. 720 The Flooding Path TLV has the format: 722 0 1 2 3 723 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 724 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 725 | Type | Length | Starting Index | 726 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 727 | Index 2 | Additional indices ... 728 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 730 Type: TBD3 732 Length: 2 * (number of indices in the path) 734 Starting index: The index of the first system in the path. 736 Index 2: The index of the next system in the path. 738 Additional indices (optional): A sequence of additional indices to 739 systems along the path. 741 5.1.5. IS-IS Flooding Request TLV 743 The Flooding Request TLV allows a system to request an adjacent node 744 to enable flooding towards it on a specific link in the case where 745 the connection to adjacent node is not part of the existing flooding 746 topology. 748 Nodes that support Dynamic Flooding MAY include the Flooding Request 749 TLV in its IIH PDUs. 751 The Flooding Request TLV has the format: 753 0 1 2 3 754 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 755 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 756 | Type | Length | Levels |R| Scope | 757 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 758 |R| ... | 759 -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 761 Type: TBD9 762 Length: 1 + number of advertised Flooding Scopes 764 Levels - the level(s) for which flooding is requested. Levels are 765 encoded as the circuit type specified in IS-IS [ISO10589] 767 R bit: MUST be 0 and is ignored on receipt. 769 Scope: Flooding Scope for which the flooding is requested as 770 defined by LSP Flooding Scope Identifier Registry defined by 771 [RFC7356]. Inclusion of flooding scopes is optional and is only 772 necessary if [RFC7356] is supported. Multiple flooding scopes MAY 773 be included. 775 Circuit Flooding Scope MUST NOT be sent in the Flooding Request TLV 776 and MUST be ignored if received. 778 When the TLV is received in a level specific LAN-Hello PDU (L1-LAN- 779 IIH or L2-LAN-IIH) only levels which match the PDU type are valid. 780 Levels which do not match the PDU type MUST be ignored on receipt. 782 When the TLV is received in a Point-to-Point Hello (P2P-IIH) only 783 levels which are supported by the established adjacency are valid. 784 Levels which are not supported by the adjacency MUST be ignored on 785 receipt. 787 If flooding was disabled on the received link due to Dynamic 788 Flooding, then flooding MUST be temporarily enabled over the link for 789 the specified Circuit Type(s) and Flooding Scope(s) received in the 790 in the Flooding Request TLV. Flooding MUST be enabled until the 791 Circuit Type or Flooding Scope is no longer advertised in the 792 Flooding Request TLV or the TLV no longer appears in IIH PDUs 793 received on the link. 795 When the flooding is temporarily enabled on the link for any Circuit 796 Type or Flooding Scope due to received Flooding Request TLV, the 797 receiver MUST perform standard database synchronization for the 798 corresponding Circuit Type(s) and Flooding Scope(s) on the link. In 799 the case of IS-IS, this results in setting SRM bit for all related 800 LSPs on the link and sending CSNPs. 802 So long as the Flooding Request TLV is being received flooding MUST 803 NOT be disabled for any of the Circuit Types or Flooding Scopes 804 present in the Flooding Request TLV even if the connection between 805 the neighbors is removed from the flooding topology. Flooding for 806 such Circuit Types or Flooding Scopes MUST continue on the link and 807 be considered as temporarily enabled. 809 5.1.6. IS-IS LEEF Advertisement 811 In support of advertising which edges are currently enabled in the 812 flooding topology, an implementation MAY indicate that a link is part 813 of the flooding topology by advertising a bit value in the Link 814 Attributes sub-TLV defined by [RFC5029]. 816 The following bit value is defined by this document: 818 Local Edge Enabled for Flooding (LEEF) - suggested value 4 (to be 819 assigned by IANA) 821 5.2. OSPF LSAs and TLVs 823 This section defines new LSAs and TLVs for both OSPFv2 and OSPFv3. 825 Following objects are added: 827 1. A TLV that is used to advertise the preference for becoming Area 828 Leader. 830 2. A TLV that is used to indicate the support for Dynamic Flooding 831 and the algorithms that the advertising node supports for 832 distributed mode, if any. 834 3. OSPFv2 Opaque LSA and OSPFv3 LSA to advertise the flooding 835 topology for centralized mode. 837 4. A TLV to carry the list of Router IDs that comprise the flooding 838 topology for the area. 840 5. A TLV to carry a path which is part of the flooding topology. 842 6. The bit in the LLS Type 1 Extended Options and Flags requests 843 flooding from the adjacent node. 845 5.2.1. OSPF Area Leader Sub-TLV 847 The usage of the OSPF Area Leader Sub-TLV is identical to IS-IS and 848 is described in Section 5.1.1. 850 The OSPF Area Leader Sub-TLV is used by both OSPFv2 and OSPFv3. 852 The OSPF Area Leader Sub-TLV is advertised as a top-level TLV of the 853 RI LSA that is defined in [RFC7770] and has the following format: 855 0 1 2 3 856 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 857 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 858 | Type | Length | 859 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 860 | Priority | Algorithm | Reserved | 861 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 863 Type: TBD4 865 Length: 4 octets 867 Priority: 0-255, unsigned integer 869 Algorithm: as defined in Section 5.1.1. 871 5.2.2. OSPF Dynamic Flooding Sub-TLV 873 The usage of the OSPF Dynamic Flooding Sub-TLV is identical to IS-IS 874 and is described in Section 5.1.2. 876 The OSPF Dynamic Flooding Sub-TLV is used by both OSPFv2 and OSPFv3. 878 The OSPF Dynamic Flooding Sub-TLV is advertised as a top-level TLV of 879 the RI LSA that is defined in [RFC7770] and has the following format: 881 0 1 2 3 882 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 883 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 884 | Type | Length | 885 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 886 | Algorithm ... | | 887 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 889 Type: TBD8 891 Length: number of Algorithms 893 Algorithm: as defined in Section 5.1.1. 895 5.2.3. OSPFv2 Dynamic Flooding Opaque LSA 897 The OSPFv2 Dynamic Flooding Opaque LSA is only used in centralized 898 mode. 900 The OSPFv2 Dynamic Flooding Opaque LSA is used to advertise 901 additional data related to the dynamic flooding in OSPFv2. OSPFv2 902 Opaque LSAs are described in [RFC5250]. 904 Multiple OSPFv2 Dynamic Flooding Opaque LSAs can be advertised by an 905 OSPFv2 router. The flooding scope of the OSPFv2 Dynamic Flooding 906 Opaque LSA is area-local. 908 The format of the OSPFv2 Dynamic Flooding Opaque LSA is as follows: 910 0 1 2 3 911 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 912 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 913 | LS age | Options | LS Type | 914 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 915 | TBD5 | Opaque ID | 916 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 917 | Advertising Router | 918 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 919 | LS sequence number | 920 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 921 | LS checksum | Length | 922 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 923 | | 924 +- TLVs -+ 925 | ... | 927 OSPFv2 Dynamic Flooding Opaque LSA 929 The opaque type used by OSPFv2 Dynamic Flooding Opaque LSA is TBD. 930 The opaque type is used to differentiate the various type of OSPFv2 931 Opaque LSAs and is described in section 3 of [RFC5250]. The LS Type 932 is 10. The LSA Length field [RFC2328] represents the total length 933 (in octets) of the Opaque LSA including the LSA header and all TLVs 934 (including padding). 936 The Opaque ID field is an arbitrary value used to maintain multiple 937 Dynamic Flooding Opaque LSAs. For OSPFv2 Dynamic Flooding Opaque 938 LSAs, the Opaque ID has no semantic significance other than to 939 differentiate Dynamic Flooding Opaque LSAs originated by the same 940 OSPFv2 router. 942 The format of the TLVs within the body of the OSPFv2 Dynamic Flooding 943 Opaque LSA is the same as the format used by the Traffic Engineering 944 Extensions to OSPF [RFC3630]. 946 The Length field defines the length of the value portion in octets 947 (thus a TLV with no value portion would have a length of 0). The TLV 948 is padded to 4-octet alignment; padding is not included in the length 949 field (so a 3-octet value would have a length of 3, but the total 950 size of the TLV would be 8 octets). Nested TLVs are also 32-bit 951 aligned. For example, a 1-octet value would have the length field 952 set to 1, and 3 octets of padding would be added to the end of the 953 value portion of the TLV. The padding is composed of zeros. 955 5.2.4. OSPFv3 Dynamic Flooding LSA 957 The OSPFv3 Dynamic Flooding Opaque LSA is only used in centralized 958 mode. 960 The OSPFv3 Dynamic Flooding LSA is used to advertise additional data 961 related to the dynamic flooding in OSPFv3. 963 The OSPFv3 Dynamic Flooding LSA has a function code of TBD. The 964 flooding scope of the OSPFv3 Dynamic Flooding LSA is area-local. The 965 U bit will be set indicating that the OSPFv3 Dynamic Flooding LSA 966 should be flooded even if it is not understood. The Link State ID 967 (LSID) value for this LSA is the Instance ID. OSPFv3 routers MAY 968 advertise multiple Dynamic Flooding Opaque LSAs in each area. 970 The format of the OSPFv3 Dynamic Flooding LSA is as follows: 972 0 1 2 3 973 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 974 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 975 | LS age |1|0|1| TBD6 | 976 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 977 | Link State ID | 978 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 979 | Advertising Router | 980 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 981 | LS sequence number | 982 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 983 | LS checksum | Length | 984 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 985 | | 986 +- TLVs -+ 987 | ... | 989 OSPFv3 Dynamic Flooding LSA 991 5.2.5. OSPF Area Router ID TLVs 993 In OSPF new TLVs are introduced to advertise indeces associated with 994 nodes and Broadcast/NBMA networks. Due to identifier differences 995 between OSPFv2 and OSPFv3 two different TLVs are defined as decribed 996 in the following sub-sections. 998 The OSPF Area Router ID TLVs are used by the Area Leader to enumerate 999 the Router IDs that it has used in computing the flooding topology. 1000 This includes the identifiers associated with Broadcast/NBMA networks 1001 as defined for Network LSAs. Conceptually, the Area Leader creates a 1002 list of Router IDs for all routers in the area, assigning indices to 1003 each router, starting with index 0. 1005 5.2.5.1. OSPFv2 Area Router ID TLV 1007 This TLV is a top level TLV of the OSPFv2 Dynamic Flooding Opaque 1008 LSA. 1010 Because the space in a single OSPFv2 Area Router IDs TLV is limited, 1011 more than one TLV may be required to encode all of the Router IDs in 1012 the area. This TLV may also occur in multiple OSPFv2 Dynamic 1013 Flooding Opaque LSAs so that all Router IDs can be advertised. 1015 Each entry in the OSPFv2 Area Router IDs TLV represents either a node 1016 or a Broadcast/NBMA network identifier. An entry has the following 1017 format: 1019 0 1 2 3 1020 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 1021 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1022 | Conn Type | Reserved | 1023 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1024 | Originating Router ID/DR Address | 1025 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1027 where 1029 Conn Type - 1 byte 1030 The following values are defined: 1031 1 - Router 1032 2 - Designated Router 1034 Reserved - 3 bytes 1035 MUST be transmitted as 0 and MUST be ignored on receipt 1037 Originating Router ID/DR Address - 4 bytes 1038 As indicated by the ID Type 1040 OSPFv2 Router IDs TLV Entry 1042 The format of the Area Router IDs TLV is: 1044 0 1 2 3 1045 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 1046 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1047 | Type | Length | 1048 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1049 | Starting Index |L| Flags | Reserved | 1050 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1051 | | 1052 +- OSPFv2 Router ID TLV Entry -+ 1053 | ... | 1055 OSPFv2 Area Router IDs TLV 1057 TLV Type: 1 1059 TLV Length: 4 + (8 * the number TLV entries) 1061 Starting index: The index of the first Router ID that appears in 1062 this TLV. 1064 L (Last): This bit is set if the index of the last system ID that 1065 appears in this TLV is equal to the last index in the full list of 1066 Rourer IDs for the area. 1068 OSPFv2 Router ID TLV Entries: A concatenated list of Router ID TLV 1069 Entries for the area. 1071 If there are multiple OSPFv2 Area Router ID TLVs with the L bit set 1072 advertised by the same router, the TLV which specifies the smaller 1073 maximum index is used and the other TLV(s) with L bit set are 1074 ignored. TLVs which specify Router IDs with indices greater than 1075 that specified by the TLV with the L bit set are also ignored. 1077 5.2.5.2. OSPFv3 Area Router ID TLV 1079 This TLV is a top level TLV of the OSPFv3 Dynamic Flooding LSA. 1081 Because the space in a single OSPFv3 Area Router ID TLV is limited, 1082 more than one TLV may be required to encode all of the Router IDs in 1083 the area. This TLV may also occur in multiple OSPFv3 Dynamic 1084 Flooding Opaque LSAs so that all Router IDs can be advertised. 1086 Each entry in the OSPFv3 Area Router IDs TLV represents either a 1087 router or a Broadcast/NBMA network identifier. An entry has the 1088 following format: 1090 0 1 2 3 1091 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 1092 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1093 | Conn Type | Reserved | 1094 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1095 | Originating Router ID (always present) | 1096 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1097 | Interface ID (present for DRs) | 1098 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1100 where 1102 Conn Type - 1 byte 1103 The following values are defined: 1104 1 - Router 1105 2 - Designated Router 1107 Reserved - 3 bytes 1108 MUST be transmitted as 0 and MUST be ignored on receipt 1110 Originating Router ID - 4 bytes 1112 Interface ID - 4 bytes 1113 This field MUST be present when Conn Type indicates Designated 1114 Router. 1115 This field MUST NOT be present when Conn Type indicates Router. 1117 OSPFv3 Router ID TLV Entry 1119 The format of the OSPFv3Area Router IDs TLV is: 1121 0 1 2 3 1122 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 1123 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1124 | Type | Length | 1125 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1126 | Starting Index |L| Flags | Reserved | 1127 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1128 | | 1129 +- OSPFv3 Router ID TLV Entry -+ 1130 | ... | 1132 OSPFv3 Area Router IDs TLV 1134 TLV Type: 1 1135 TLV Length: 4 + sum of the lengths of all TLV entries 1137 Starting index: The index of the first Router ID that appears in 1138 this TLV. 1140 L (Last): This bit is set if the index of the last router ID that 1141 appears in this TLV is equal to the last index in the full list of 1142 Router IDs for the area. 1144 OSPFv2 Router ID TLV Entries: A concatenated list of Router ID TLV 1145 Entries for the area. 1147 If there are multiple OSPFv3 Area Router ID TLVs with the L bit set 1148 advertised by the same router, the TLV which specifies the smaller 1149 maximum index is used and the other TLV(s) with L bit set are 1150 ignored. TLVs which specify Router IDs with indices greater than 1151 that specified by the TLV with the L bit set are also ignored. 1153 5.2.6. OSPF Flooding Path TLV 1155 The OSPF Flooding Path TLV is a top level TLV of the OSPFv2 Dynamic 1156 Flooding Opaque LSAs and OSPFv3 Dynamic Flooding LSA. 1158 The usage of the OSPF Flooding Path TLV is identical to IS-IS and is 1159 described in Section 5.1.4. 1161 The OSPF Flooding Path TLV contains a list of Router ID indices 1162 relative to the Router IDs advertised through the OSPF Area Router 1163 IDs TLV. At least 2 indices must be included in the TLV. 1165 Multiple OSPF Flooding Path TLVs can be advertised in a single OSPFv2 1166 Dynamic Flooding Opaque LSA or OSPFv3 Dynamic Flooding LSA. OSPF 1167 Flooding Path TLVs can also be advertised in multiple OSPFv2 Dynamic 1168 Flooding Opaque LSAs or OSPFv3 Dynamic Flooding LSA, if they all can 1169 not fit in a single LSA. 1171 The Flooding Path TLV has the format: 1173 0 1 2 3 1174 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 1175 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1176 | Type | Length | 1177 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1178 | Starting Index | Index 2 | 1179 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1180 | | 1181 +- Additional Indices -+ 1182 | ... | 1184 OSPF Flooding Path TLV 1186 TLV Type: 2 1188 TLV Length: 2 * (number of indices in the path) 1190 Starting index: The index of the first Router ID in the path. 1192 Index 2: The index of the next Router ID in the path. 1194 Additional indices (optional): A sequence of additional indices to 1195 Router IDs along the path. 1197 5.2.7. OSPF Flooding Request Bit 1199 A single new option bit, the Flooding-Request (FR-bit), is defined in 1200 the LLS Type 1 Extended Options and Flags field [RFC2328]. The FR- 1201 bit allows a router to request an adjacent node to enable flooding 1202 towards it on a specific link in the case where the connection to 1203 adjacent node is not part of the current flooding topology. 1205 Nodes that support Dynamic Flooding MAY include FR-bit in its OSPF 1206 LLS Extended Options and Flags TLV. 1208 If FR-bit is signalled for an area for which the flooding on the link 1209 was disabled due to Dynamic Flooding, the flooding MUST be 1210 temporarily enabled over such link and area. Flooding MUST be 1211 enabled until FR-bit is no longer advertised in the OSPF LLS Extended 1212 Options and Flags TLV or the OSPF LLS Extended Options and Flags TLV 1213 no longer appears in the OSPF Hellos. 1215 When the flooding is temporarily enabled on the link for any area due 1216 to received FR-bit in OSPF LLS Extended Options and Flags TLV, the 1217 receiver MUST perform standard database synchronization for the 1218 corresponding area(s) on the link. If the adjacency is already in 1219 the FULL state, mechanism specified in [RFC4811] MUST be used for 1220 database resynchronization. 1222 So long as the FR-bit is being received in the OSPF LLS Extended 1223 Options and Flags TLV for an area, flooding MUST NOT be disabled in 1224 such area even if the connection between the neighbors is removed 1225 from the flooding topology. Flooding for such area MUST continue on 1226 the link and be considered as temporarily enabled. 1228 5.2.8. OSPF LEEF Advertisement 1230 In support of advertising which edges are currently enabled in the 1231 flooding topology, an implementation MAY indicate that a link is part 1232 of the flooding topology. The OSPF Link Attributes Bits TLV is 1233 defined to support this advertisement. 1235 0 1 2 3 1236 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 1237 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1238 | Type | Length | 1239 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1240 | Link Attribute Bits | 1241 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1242 | | 1243 +- Additional Link Attribute Bits -+ 1244 | ... | 1246 OSPF Link Attributes Bits TLV 1248 Type: TBD and specific to OSPFv2 and OSPFv3 1250 Length: size of the Link Attribute Bits in bytes. It MUST be a 1251 multiple of 4 bytes. 1253 The following bits are defined: 1255 Bit #0: - Local Edge Enabled for Flooding (LEEF) 1257 OSPF Link-attribute Bits TLV appears as: 1259 1. a sub-TLV of the OSPFv2 Extended Link TLV [RFC7684] 1261 2. a sub-TLV of the OSPFv3 Router-Link TLV [RFC8362] 1263 6. Behavioral Specification 1265 In this section, we specify the detailed behaviors of the nodes 1266 participating in the IGP. 1268 6.1. Terminology 1270 We define some terminology here that is used in the following 1271 sections: 1273 A node is considered reachable if it is part of the connected 1274 network graph. Note that this is independent of any constraints 1275 which may be considered when performing IGP SPT calculation (e.g., 1276 link metrics, OL bit state, etc.). Two-way-connectivity check 1277 MUST be performed before including an edge in the connected 1278 network graph. 1280 Node is connected to the flooding topology, if it has at least one 1281 local link, which is part of the flooding topology. 1283 Node is disconnected from the flooding topology when it is not 1284 connected to the flooding topology. 1286 Current flooding topology - latest version of the flooding 1287 topology received (in case of the centralized mode) or calculated 1288 locally (in case of the distributed mode). 1290 6.2. Flooding Topology 1292 The flooding topology MUST include all reachable nodes in the area. 1294 If a node's reachability changes, the flooding topology MUST be 1295 recalculated. In centralized mode, the Area Leader MUST advertise a 1296 new flooding topology. 1298 If a node becomes disconnected from the current flooding topology but 1299 is still reachable then a new flooding topology MUST be calculated. 1300 In centralized mode the Area Leader MUST advertise the new flooding 1301 topology. 1303 The flooding topology SHOULD be bi-connected. 1305 6.3. Leader Election 1307 Any node that is capable MAY advertise its eligibility to become Area 1308 Leader. 1310 Nodes that are not reachable are not eligible as Area Leader. Nodes 1311 that do not advertise their eligibility to become Area Leader are not 1312 eligible. Amongst the eligible nodes, the node with the numerically 1313 highest priority is the Area Leader. If multiple nodes all have the 1314 highest priority, then the node with the numerically highest system 1315 identifier in the case of IS-IS, or Router-ID in the case of OSPFv2 1316 and OSPFv3 is the Area Leader. 1318 6.4. Area Leader Responsibilities 1320 If the Area Leader operates in centralized mode, it MUST advertise 1321 algorithm 0 in its Area Leader Sub-TLV. It also MUST compute and 1322 advertise a flooding topology for the area. The Area Leader may 1323 update the flooding topology at any time, however, it should not 1324 destabilize the network with undue or overly frequent topology 1325 changes. 1327 If the Area Leader operates in centralized mode and needs to 1328 advertises a new flooding topology, it floods a new flooding topology 1329 on both the new and old flooding topologies. 1331 6.5. Distributed Flooding Topology Calculation 1333 If the Area Leader advertises a non-zero algorithm in its Area Leader 1334 Sub-TLV, all nodes in the area that support Dynamic Flooding and the 1335 value of algorithm advertised by the Area Leader MUST compute the 1336 flooding topology based on the Area Leader's advertised algorithm. 1338 Nodes that do not support the value of algorithm advertised by the 1339 Area Leader MUST continue to use standard flooding mechanism as 1340 defined by the protocol. 1342 Nodes that do not support the value of algorithm advertised by the 1343 Area Leader MUST be considered as Dynamic Flooding incapable nodes by 1344 the Area Leader. 1346 If the value of the algorithm advertised by the Area Leader is from 1347 the range 128-254 (private distributed algorithms), it is the 1348 responsibility of the network operator to guarantee that all nodes in 1349 the area have a common understanding of what the given algorithm 1350 value represents. 1352 6.6. Use of LANs in the Flooding Topology 1354 Use of LANs in the flooding topology differs depending on whether the 1355 area is operating in Centralized or Distributed mode. 1357 6.6.1. Use of LANs in Centralized mode 1359 As specified in Section 4.5, when a LAN is advertised as part of the 1360 flooding topology, all nodes connected to the LAN are assumed to be 1361 using the LAN as part of the flooding topology. This assumption is 1362 made to reduce the size of the Flooding Topology advertisement. 1364 6.6.2. Use of LANs in Distributed Mode 1366 In distributed mode, the flooding topology is NOT advertised, 1367 therefore the space consumed to advertise it is not a concern. It is 1368 therefore possible to assign only a subset of the nodes connected to 1369 the LAN to use the LAN as part of the flooding topology. Doing so 1370 may further optimize flooding by reducing the amount of redundant 1371 flooding on a LAN. However, support of flooding only by a subset of 1372 the nodes connected to a LAN requires some modest - but backwards 1373 compatible - changes in the way flooding is performed on a LAN. 1375 6.6.2.1. Partial flooding on a LAN in IS-IS 1377 Designated Intermediate System (DIS) for a LAN MUST use standard 1378 flooding behavior: 1380 Non-DIS nodes whose connection to the LAN is included in the flooding 1381 topology MUST use standard flooding behavior. 1383 Non-DIS nodes whose connection to the LAN is NOT included in the 1384 flooding topology behave as follows: 1386 o Received CSNPs from the DIS are ignored 1388 o PSNPs are NOT originated on the LAN 1390 o LSPs received on the LAN which are newer than the corresponding 1391 LSP present in the LSPDB are retained and flooded on all local 1392 circuits which are part of the flooding topology (i.e., do not 1393 discard newer LSPs simply because they were received on a LAN 1394 which the receiving node is not using for flooding) 1396 o LSPs received on the LAN which are older or same as the 1397 corresponding LSP present in the LSPDB are silently discarded 1399 o LSPs received on links other than the LAN are NOT flooded on the 1400 LAN 1402 NOTE: If any node connected to the LAN requests the enablement of 1403 temporary flooding all nodes revert to standard flooding behavior. 1405 6.6.2.2. Partial Flooding on a LAN in OSPF 1407 Designated Router (DR) and Backup Designated Router (BDR) for LANs 1408 MUST use standard flooding behavior. 1410 Non-DR/BDR nodes whose connection to the LAN is included in the 1411 flooding topology use standard flooding behavior. 1413 Non-DR/BDR nodes whose connection to the LAN is NOT included in the 1414 flooding topology behave as follows: 1416 o LSAs received on the LAN are acknowledged to DR/BDR 1418 o LSAs received on interfaces other than the LAN are NOT flooded on 1419 the LAN 1421 NOTE: If any node connected to the LAN requests the enablement of 1422 temporary flooding all nodes revert to standard flooding behavior. 1424 NOTE: The sending of LSA acks by nodes NOT using the LAN as part of 1425 the flooding topology eliminates the need for changes on the part of 1426 the DR/BDR - which might Include nodes which do not support the 1427 flooding optimizations. 1429 6.7. Flooding Behavior 1431 Nodes that support Dynamic Flooding MUST use the flooding topology 1432 for flooding when possible, and MUST NOT revert to standard flooding 1433 when a valid flooding topology is available. 1435 In some cases a node that supports Dynamic Flooding may need to add a 1436 local link(s) to the flooding topology temporarily, even though the 1437 link(s) is not part of the calculated flooding topology. This is 1438 termed "temporary flooding" and is discussed in Section 6.8.1. 1440 The flooding topology is calculated locally in the case of 1441 distributed mode. In centralized mode the flooding topology is 1442 advertised in the area link state database. Received link state 1443 updates, whether received on a link that is in the flooding topology 1444 or on a link that is not in the flooding topology, MUST be flooded on 1445 all links that are in the flooding topology, except for the link on 1446 which the update was received. 1448 In centralized mode, if multiple flooding topologies are present in 1449 the area link state database, the node SHOULD flood on each of these 1450 topologies. 1452 When the flooding topology changes on a node, either as a result of 1453 the local computation in distributed mode or as a result of the 1454 advertisement from the Area Leader in centralized mode, the node MUST 1455 continue to flood on both the old and new flooding topology for a 1456 limited amount of time. This is required to provide all nodes 1457 sufficient time to migrate to the new flooding topology. 1459 6.8. Treatment of Topology Events 1461 In this section, we explicitly consider a variety of different 1462 topological events in the network and how Dynamic Flooding should 1463 address them. 1465 6.8.1. Temporary Addition of Link to Flooding Topology 1467 In some cases a node that supports Dynamic Flooding may need to add a 1468 local link(s) to the flooding topology temporarily, even though the 1469 link(s) is not part of the calculated flooding topology. We refer to 1470 this as "temporary flooding" on the link. 1472 When temporary flooding is enabled on the link, the flooding needs to 1473 be enabled from both directions on the link. To achieve that, the 1474 following steps MUST be performed: 1476 Link State Database needs to be re-synchronised on the link. This 1477 is done using the standard protocol mechanisms. In the case of 1478 IS-IS, this results in setting SRM bit for all LSPs on the circuit 1479 and sending compete set of CSNPs on it. In OSPF, the mechanism 1480 specified in [RFC4811] is used. 1482 Flooding is enabled locally on the link. 1484 Flooding is requested from the neighbor using the mechanism 1485 specified in section Section 5.1.5 or Section 5.2.7. 1487 The request for temporary flooding is withdrawn on the link when all 1488 of the following conditions are met: 1490 Node itself is connected to the current flooding topology. 1492 Adjacent node is connected to the current flooding topology. 1494 Any change in the flooding topology MUST result in evaluation of the 1495 above conditions for any link on which the temporary flooding was 1496 enabled. 1498 Temporary flooding is stopped on the link when both adjacent nodes 1499 stop requesting temporary flooding on the link. 1501 6.8.2. Local Link Addition 1503 If a local link is added to the topology, the protocol will form a 1504 normal adjacency on the link and update the appropriate link state 1505 advertisements for the nodes on either end of the link. These link 1506 state updates will be flooded on the flooding topology. 1508 In centralized mode, the Area Leader, upon receiving these updates, 1509 may choose to retain the existing flooding topology or may choose to 1510 modify the flooding topology. If it elects to change the flooding 1511 topology, it will update the flooding topology in the link state 1512 database and flood it using the new flooding topology. 1514 In distributed mode, any change in the topology, including the link 1515 addition, MUST trigger the flooding topology recalculation. This is 1516 done to ensure that all nodes converge to the same flooding topology, 1517 regardless of the time of the calculation. 1519 Temporary flooding MUST be enabled on the newly added local link, if 1520 at least one of the following conditions are met: 1522 The node on which the local link was added is not connected to the 1523 current flooding topology. 1525 The new adjacent node is not connected to the current flooding 1526 topology. 1528 Note that in this case there is no need to perform a database 1529 synchronization as part of the enablement of the temporary flooding, 1530 because it has been part of the adjacency bring-up itself. 1532 If multiple local links are added to the topology before the flooding 1533 topology is updated, temporary flooding MUST be enabled on a subset 1534 of these links. 1536 6.8.3. Node Addition 1538 If a node is added to the topology, then at least one link is also 1539 added to the topology. Section 6.8.2 applies. 1541 A node which has a large number of neighbors is at risk for 1542 introducing a local flooding storm if all neighbors are brought up at 1543 once and temporary flooding is enabled on all links simultaneously. 1544 The most robust way to address this is to limit the rate of initial 1545 adjacency formation following bootup. This both reduces unnecessary 1546 redundant flooding as part of initial database synchronization and 1547 minimizes the need for temporary flooding as it allows time for the 1548 new node to be added to the flooding topology after only a small 1549 number of adjacencies have been formed. 1551 In the event a node elects to bring up a large number of adjacencies 1552 simultaneously, a significant amount of redundant flooding may be 1553 introduced as multiple neighbors of the new node enable temporary 1554 flooding to the new node which initially is not part of the flooding 1555 topology. 1557 6.8.4. Failures of Link Not on Flooding Topology 1559 If a link that is not part of the flooding topology fails, then the 1560 adjacent nodes will update their link state advertisements and flood 1561 them on the flooding topology. 1563 In centralized mode, the Area Leader, upon receiving these updates, 1564 may choose to retain the existing flooding topology or may choose to 1565 modify the flooding topology. If it elects to change the flooding 1566 topology, it will update the flooding topology in the link state 1567 database and flood it using the new flooding topology. 1569 In distributed mode, any change in the topology, including the 1570 failure of the link that is not part of the flooding topology MUST 1571 trigger the flooding topology recalculation. This is done to ensure 1572 that all nodes converge to the same flooding topology, regardless of 1573 the time of the calculation. 1575 6.8.5. Failures of Link On the Flooding Topology 1577 If there is a failure on the flooding topology, the adjacent nodes 1578 will update their link state advertisements and flood them. If the 1579 original flooding topology is bi-connected, the flooding topology 1580 should still be connected despite a single failure. 1582 If the failed local link represented the only connection to the 1583 flooding topology on the node where the link failed, the node MUST 1584 enable temporary flooding on a subset of its local links. This 1585 allows the node to send its updated link state advertisement(s) and 1586 also keep receiving link state updates from other nodes in the 1587 network before the new flooding topology is calculated and 1588 distributed (in the case of centralized mode). 1590 In centralized mode, the Area Leader will notice the change in the 1591 flooding topology, recompute the flooding topology, and flood it 1592 using the new flooding topology. 1594 In distributed mode, all nodes supporting dynamic flooding will 1595 notice the change in the topology and recompute the new flooding 1596 topology. 1598 6.8.6. Node Deletion 1600 If a node is deleted from the topology, then at least one link is 1601 also removed from the topology. Section 6.8.4 and Section 6.8.5 1602 apply. 1604 6.8.7. Local Link Addition to the Flooding Topology 1606 If the new flooding topology is received in the case of centralized 1607 mode, or calculated locally in the case of distributed mode and the 1608 local link on the node that was not part of the flooding topology has 1609 been added to the flooding topology, the node MUST: 1611 Re-synchronize the Link State Database over the link. This is 1612 done using the standard protocol mechanisms. In the case of IS- 1613 IS, this results in setting SRM bit for all LSPs on the circuit 1614 and sending a complete set of CSNPs. In OSPF, the mechanism 1615 specified in [RFC4811] is used. 1617 Make the link part of the flooding topology and start flooding 1618 over it 1620 6.8.8. Local Link Deletion from the Flooding Topology 1622 If the new flooding topology is received in the case of centralized 1623 mode, or calculated locally in the case of distributed mode and the 1624 local link on the node that was part of the flooding topology has 1625 been removed from the flooding topology, the node MUST remove the 1626 link from the flooding topology. 1628 The node MUST keep flooding on such link for a limited amount of time 1629 to allow other nodes to migrate to the new flooding topology. 1631 If the removed local link represented the only connection to the 1632 flooding topology on the node, the node MUST enable temporary 1633 flooding on a subset of its local links. This allows the node to 1634 send its updated link state advertisement(s) and also keep receiving 1635 link state updates from other nodes in the network before the new 1636 flooding topology is calculated and distributed (in the case of 1637 centralized mode). 1639 6.8.9. Treatment of Disconnected Adjacent Nodes 1641 Every time there is a change in the flooding topology a node MUST 1642 check if there are any adjacent nodes that are disconnected from the 1643 current flooding topology. Temporary flooding MUST be enabled 1644 towards a subset of the disconnected nodes. 1646 6.8.10. Failure of the Area Leader 1648 The failure of the Area Leader can be detected by observing that it 1649 is no longer reachable. In this case, the Area Leader election 1650 process is repeated and a new Area Leader is elected. 1652 In the centralized mode, the new Area Leader will compute a new 1653 flooding topology and flood it using the new flooding topology. 1655 As an optimization, applicable to centralized mode, the new Area 1656 Leader MAY compute a new flooding topology that has as much in common 1657 as possible with the old flooding topology. This will minimize the 1658 risk of over-flooding. 1660 In the distributed mode, the new flooding topology will be calculated 1661 on all nodes that support the algorithm that is advertised by the new 1662 Area Leader. Nodes that do not support the algorithm advertised by 1663 the new Area Leader will no longer participate in Dynamic Flooding 1664 and will revert to standard flooding. 1666 6.8.11. Recovery from Multiple Failures 1668 In the unlikely event of multiple failures on the flooding topology, 1669 it may become partitioned. The nodes that remain active on the edges 1670 of the flooding topology partitions will recognize this and will try 1671 to repair the flooding topology locally by enabling temporary 1672 flooding towards the nodes that they consider disconnected from the 1673 flooding topology until a new flooding topology becomes connected 1674 again. 1676 Nodes where local failure was detected update their own link state 1677 advertisements and flood them on the remainder of the flooding 1678 topology. 1680 In centralized mode, the Area Leader will notice the change in the 1681 flooding topology, recompute the flooding topology, and flood it 1682 using the new flooding topology. 1684 In distributed mode, all nodes that actively participate in Dynamic 1685 Flooding will compute the new flooding topology. 1687 Note that this is very different from the area partition because 1688 there is still a connected network graph between the nodes in the 1689 area. The area may remain connected and forwarding may still be 1690 effective. 1692 6.8.12. Rate Limiting Temporary Flooding 1694 As discussed in the previous sections, there are events which require 1695 the introduction of temporary flooding on edges which are not part of 1696 the current flooding topology. This can occur regardless of whether 1697 the area is operating in centralized mode or distributed mode. 1699 Nodes which decide to enable temporary flooding also have to decide 1700 whether to do so on a subset of the edges which are currently not 1701 part of the flooding topology or on all the edges which are currently 1702 not part of the flooding topology. Doing the former risks a longer 1703 convergence time as it is possible that the initial set of edges 1704 enabled does not fully repair the flooding topology. Doing the 1705 latter risks introducing a flooding storm which destablizes the 1706 network. 1708 It is recommended that a node implement rate limiting on the number 1709 of edges on which it chooses to enable temporary flooding. Initial 1710 values for the number of edges to enable and the rate at which 1711 additional edges may subsequently be enabled is left as an 1712 implementation decision. 1714 7. IANA Considerations 1716 7.1. IS-IS 1718 This document requests the following code points from the "sub-TLVs 1719 for TLV 242" registry (IS-IS Router CAPABILITY TLV). 1721 Type: TBD1 1723 Description: IS-IS Area Leader Sub-TLV 1725 Reference: This document (Section 5.1.1) 1727 Type: TBD7 1729 Description: IS-IS Dynamic Flooding Sub-TLV 1731 Reference: This document (Section 5.1.2) 1733 This document requests that IANA allocate and assign code points from 1734 the "IS-IS TLV Codepoints" registry. One for each of the following 1735 TLVs: 1737 Type: TBD2 1739 Description: IS-IS Area System IDs TLV 1741 Reference: This document (Section 5.1.3) 1743 Type: TBD3 1745 Description: IS-IS Flooding Path TLV 1746 Reference: This document (Section 5.1.4) 1748 Type: TBD9 1750 Description: IS-IS Flooding Request TLV 1752 Reference: This document (Section 5.1.5) 1754 This document requests that IANA allocate a new bit value from the 1755 "link-attribute bit values for sub-TLV 19 of TLV 22" registry. 1757 Local Edge Enabled for Flooding (LEEF) - suggested value 4 (to be 1758 assigned by IANA) 1760 7.2. OSPF 1762 This document requests the following code points from the "OSPF 1763 Router Information (RI) TLVs" registry: 1765 Type: TBD4 1767 Description: OSPF Area Leader Sub-TLV 1769 Reference: This document (Section 5.2.1) 1771 Type: TBD8 1773 Description: OSPF Dynamic Flooding Sub-TLV 1775 Reference: This document (Section 5.2.2) 1777 This document requests the following code point from the "Opaque 1778 Link-State Advertisements (LSA) Option Types" registry: 1780 Type: TBD5 1782 Description: OSPFv2 Dynamic Flooding Opaque LSA 1784 Reference: This document (Section 5.2.3) 1786 This document requests the following code point from the "OSPFv3 LSA 1787 Function Codes" registry: 1789 Type: TBD6 1791 Description: OSPFv3 Dynamic Flooding LSA 1793 Reference: This document (Section 5.2.4) 1795 This document requests a new bit in LLS Type 1 Extended Options and 1796 Flags registry: 1798 Bit Position: TBD10 1800 Description: Flooding Request bit 1802 Reference: This document (Section 5.2.7) 1804 This document requests the following code point from the "OSPFv2 1805 Extended Link TLV Sub-TLVs" registry: 1807 Type: TBD11 1809 Description: OSPFv2 Link Attributes Bits Sub-TLV 1811 Reference: This document (Section 5.2.8) 1813 This document requests the following code point from the "OSPFv3 1814 Extended LSA Sub-TLVs" registry: 1816 Type: TBD12 1818 Description: OSPFv3 Link Attributes Bits Sub-TLV 1820 Reference: This document (Section 5.2.8) 1822 7.2.1. OSPF Dynamic Flooding LSA TLVs Registry 1824 This specification also requests a new registry - "OSPF Dynamic 1825 Flooding LSA TLVs". New values can be allocated via IETF Review or 1826 IESG Approval 1828 The "OSPF Dynamic Flooding LSA TLVs" registry will define top-level 1829 TLVs for the OSPFv2 Dynamic Flooding Opaque LSA and OSPFv3 Dynamic 1830 Flooding LSAs. It should be added to the "Open Shortest Path First 1831 (OSPF) Parameters" registries group. 1833 The following initial values are allocated: 1835 Type: 0 1837 Description: Reserved 1839 Reference: This document 1841 Type: 1 1842 Description: OSPF Area Router IDs TLV 1844 Reference: This document (Section 5.2.5) 1846 Type: 2 1848 Description: OSPF Flooding Path TLV 1850 Reference: This document (Section 5.2.6) 1852 Types in the range 32768-33023 are for experimental use; these will 1853 not be registered with IANA, and MUST NOT be mentioned by RFCs. 1855 Types in the range 33024-65535 are not to be assigned at this time. 1856 Before any assignments can be made in the 33024-65535 range, there 1857 MUST be an IETF specification that specifies IANA Considerations that 1858 covers the range being assigned. 1860 7.2.2. OSPF Link Attributes Sub-TLV Bit Values Registry 1862 This specification also requests a new registry - "OSPF Link 1863 Attributes Sub-TLV Bit Values". New values can be allocated via IETF 1864 Review or IESG Approval 1866 The "OSPF Link Attributes Sub-TLV Bit Values" registry defines Link 1867 Attribute bit values for the OSPFv2 Link Attributes Sub-TLV and 1868 OSPFv3 Link Attributes Sub-TLV. It should be added to the "Open 1869 Shortest Path First (OSPF) Parameters" registries group. 1871 The following initial value is allocated: 1873 Bit Number: 0 1875 Description: Local Edge Enabled for Flooding(LEEF) 1877 Reference: This document (Section 5.2.8) 1879 7.3. IGP 1881 IANA is requested to set up a registry called "IGP Algorithm Type For 1882 Computing Flooding Topology" under an existing "Interior Gateway 1883 Protocol (IGP) Parameters" IANA registries. 1885 Values in this registry come from the range 0-255. 1887 The initial values in the IGP Algorithm Type For Computing Flooding 1888 Topology registry are: 1890 0: Reserved for centralized mode. Individual values are are to be 1891 assigned according to the "Specification Required" policy defined 1892 in [RFC8126] 1894 1-127: Available for standards action.Individual values are are to 1895 be assigned according to the "Private Use" policy defined in 1896 [RFC8126] 1898 128-254: Reserved for private use. 1900 255: Reserved. 1902 8. Security Considerations 1904 This document introduces no new security issues. Security of routing 1905 within a domain is already addressed as part of the routing protocols 1906 themselves. This document proposes no changes to those security 1907 architectures. 1909 It is possible that an attacker could become Area Leader and 1910 introduce a flawed flooding algorithm into the network thus 1911 compromising the operation of the protocol. Authentication methods 1912 as describe in [RFC5304] and [RFC5310] for IS-IS, [RFC2328] and 1913 [RFC7474] for OSPFv2 and [RFC5340] and [RFC4552] for OSPFv3 SHOULD be 1914 used to prevent such attack. 1916 9. Acknowledgements 1918 The authors would like to thank Sarah Chen for her contribution to 1919 this work. 1921 The authors would like to thank Zeqing (Fred) Xia, Naiming Shen, Adam 1922 Sweeney and Olufemi Komolafe for their helpful comments. 1924 The authors would like to thank Tom Edsall for initially introducing 1925 them to the problem. 1927 Advertising Local Edges Enabled for Flooding (LEEF) is based on an 1928 idea proposed in [I-D.cc-lsr-flooding-reduction]. We wish to thank 1929 the authors of that draft - in particular Huaimo Chen. 1931 10. References 1933 10.1. Normative References 1935 [ISO10589] 1936 International Organization for Standardization, 1937 "Intermediate System to Intermediate System Intra-Domain 1938 Routing Exchange Protocol for use in Conjunction with the 1939 Protocol for Providing the Connectionless-mode Network 1940 Service (ISO 8473)", ISO/IEC 10589:2002, Nov. 2002. 1942 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1943 Requirement Levels", BCP 14, RFC 2119, 1944 DOI 10.17487/RFC2119, March 1997, 1945 . 1947 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 1948 DOI 10.17487/RFC2328, April 1998, 1949 . 1951 [RFC4552] Gupta, M. and N. Melam, "Authentication/Confidentiality 1952 for OSPFv3", RFC 4552, DOI 10.17487/RFC4552, June 2006, 1953 . 1955 [RFC5029] Vasseur, JP. and S. Previdi, "Definition of an IS-IS Link 1956 Attribute Sub-TLV", RFC 5029, DOI 10.17487/RFC5029, 1957 September 2007, . 1959 [RFC5250] Berger, L., Bryskin, I., Zinin, A., and R. Coltun, "The 1960 OSPF Opaque LSA Option", RFC 5250, DOI 10.17487/RFC5250, 1961 July 2008, . 1963 [RFC5304] Li, T. and R. Atkinson, "IS-IS Cryptographic 1964 Authentication", RFC 5304, DOI 10.17487/RFC5304, October 1965 2008, . 1967 [RFC5310] Bhatia, M., Manral, V., Li, T., Atkinson, R., White, R., 1968 and M. Fanto, "IS-IS Generic Cryptographic 1969 Authentication", RFC 5310, DOI 10.17487/RFC5310, February 1970 2009, . 1972 [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF 1973 for IPv6", RFC 5340, DOI 10.17487/RFC5340, July 2008, 1974 . 1976 [RFC5613] Zinin, A., Roy, A., Nguyen, L., Friedman, B., and D. 1977 Yeung, "OSPF Link-Local Signaling", RFC 5613, 1978 DOI 10.17487/RFC5613, August 2009, 1979 . 1981 [RFC7120] Cotton, M., "Early IANA Allocation of Standards Track Code 1982 Points", BCP 100, RFC 7120, DOI 10.17487/RFC7120, January 1983 2014, . 1985 [RFC7356] Ginsberg, L., Previdi, S., and Y. Yang, "IS-IS Flooding 1986 Scope Link State PDUs (LSPs)", RFC 7356, 1987 DOI 10.17487/RFC7356, September 2014, 1988 . 1990 [RFC7474] Bhatia, M., Hartman, S., Zhang, D., and A. Lindem, Ed., 1991 "Security Extension for OSPFv2 When Using Manual Key 1992 Management", RFC 7474, DOI 10.17487/RFC7474, April 2015, 1993 . 1995 [RFC7684] Psenak, P., Gredler, H., Shakir, R., Henderickx, W., 1996 Tantsura, J., and A. Lindem, "OSPFv2 Prefix/Link Attribute 1997 Advertisement", RFC 7684, DOI 10.17487/RFC7684, November 1998 2015, . 2000 [RFC7770] Lindem, A., Ed., Shen, N., Vasseur, JP., Aggarwal, R., and 2001 S. Shaffer, "Extensions to OSPF for Advertising Optional 2002 Router Capabilities", RFC 7770, DOI 10.17487/RFC7770, 2003 February 2016, . 2005 [RFC7981] Ginsberg, L., Previdi, S., and M. Chen, "IS-IS Extensions 2006 for Advertising Router Information", RFC 7981, 2007 DOI 10.17487/RFC7981, October 2016, 2008 . 2010 [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for 2011 Writing an IANA Considerations Section in RFCs", BCP 26, 2012 RFC 8126, DOI 10.17487/RFC8126, June 2017, 2013 . 2015 [RFC8362] Lindem, A., Roy, A., Goethals, D., Reddy Vallem, V., and 2016 F. Baker, "OSPFv3 Link State Advertisement (LSA) 2017 Extensibility", RFC 8362, DOI 10.17487/RFC8362, April 2018 2018, . 2020 10.2. Informative References 2022 [Clos] Clos, C., "A Study of Non-Blocking Switching Networks", 2023 The Bell System Technical Journal Vol. 32(2), DOI 2024 10.1002/j.1538-7305.1953.tb01433.x, March 1953, 2025 . 2027 [I-D.cc-lsr-flooding-reduction] 2028 Chen, H., Cheng, D., Toy, M., Yang, Y., Wang, A., Liu, X., 2029 Fan, Y., and L. Liu, "LS Distributed Flooding Reduction", 2030 draft-cc-lsr-flooding-reduction-03 (work in progress), 2031 March 2019. 2033 [Leiserson] 2034 Leiserson, C., "Fat-Trees: Universal Networks for 2035 Hardware-Efficient Supercomputing", IEEE Transactions on 2036 Computers 34(10):892-901, 1985. 2038 [RFC2973] Balay, R., Katz, D., and J. Parker, "IS-IS Mesh Groups", 2039 RFC 2973, DOI 10.17487/RFC2973, October 2000, 2040 . 2042 [RFC3630] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering 2043 (TE) Extensions to OSPF Version 2", RFC 3630, 2044 DOI 10.17487/RFC3630, September 2003, 2045 . 2047 [RFC4811] Nguyen, L., Roy, A., and A. Zinin, "OSPF Out-of-Band Link 2048 State Database (LSDB) Resynchronization", RFC 4811, 2049 DOI 10.17487/RFC4811, March 2007, 2050 . 2052 [RFC7938] Lapukhov, P., Premji, A., and J. Mitchell, Ed., "Use of 2053 BGP for Routing in Large-Scale Data Centers", RFC 7938, 2054 DOI 10.17487/RFC7938, August 2016, 2055 . 2057 Authors' Addresses 2059 Tony Li (editor) 2060 Arista Networks 2061 5453 Great America Parkway 2062 Santa Clara, California 95054 2063 USA 2065 Email: tony.li@tony.li 2066 Peter Psenak (editor) 2067 Cisco Systems, Inc. 2068 Eurovea Centre, Central 3 2069 Pribinova Street 10 2070 Bratislava 81109 2071 Slovakia 2073 Email: ppsenak@cisco.com 2075 Les Ginsberg 2076 Cisco Systems, Inc. 2077 510 McCarthy Blvd. 2078 Milpitas, California 95035 2079 USA 2081 Email: ginsberg@cisco.com 2083 Tony Przygienda 2084 Juniper Networks, Inc. 2085 1194 N. Mathilda Ave 2086 Sunnyvale, California 94089 2087 USA 2089 Email: prz@juniper.net 2091 Dave Cooper 2092 CenturyLink 2093 1025 Eldorado Blvd 2094 Broomfield, Colorado 80021 2095 USA 2097 Email: Dave.Cooper@centurylink.com 2099 Luay Jalil 2100 Verizon 2101 Richardson, Texas 75081 2102 USA 2104 Email: luay.jalil@verizon.com 2105 Srinath Dontula 2106 ATT 2107 200 S Laurel Ave 2108 Middletown, New Jersey 07748 2109 USA 2111 Email: sd947e@att.com