idnits 2.17.00 (12 Aug 2021) /tmp/idnits11140/draft-ietf-lsr-dynamic-flooding-02.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 27, 2019) is 1090 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 2011, but no explicit reference was found in the text == Unused Reference: 'RFC7120' is defined on line 2016, 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 28, 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 27, 2019 17 Dynamic Flooding on Dense Graphs 18 draft-ietf-lsr-dynamic-flooding-02 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 28, 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 . . . . . . . . . . . . . . . . . . 29 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 . . . . . . . . . . 31 105 6.6.1. Use of LANs in Centralized mode . . . . . . . . . . . 31 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 . . . . . . . . 32 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 . . . . . . . . . . . . . . . . . 34 113 6.8.3. Node Addition . . . . . . . . . . . . . . . . . . . . 35 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 . . . . . . . . . . . . . . . . . . . . 36 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 . . . . . . 37 120 6.8.10. Failure of the Area Leader . . . . . . . . . . . . . 37 121 6.8.11. Recovery from Multiple Failures . . . . . . . . . . . 37 122 6.8.12. Rate Limiting Temporary Flooding . . . . . . . . . . 38 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 . . . . . . . 41 127 7.2.2. OSPF Link Attributes Sub-TLV Bit Values Registry . . 41 128 7.3. IGP . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 129 8. Security Considerations . . . . . . . . . . . . . . . . . . . 42 130 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 43 131 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 43 132 10.1. Normative References . . . . . . . . . . . . . . . . . . 43 133 10.2. Informative References . . . . . . . . . . . . . . . . . 45 134 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 46 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 | Number of IDs | Reserved | 1023 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1024 | | 1025 +- Originating Router ID/DR Address -+ 1026 | ... | 1028 where 1030 Conn Type - 1 byte 1031 The following values are defined: 1032 1 - Router 1033 2 - Designated Router 1035 Number of IDs - 2 bytes 1037 Reserved - 1 byte 1038 MUST be transmitted as 0 and MUST be ignored on receipt 1040 Originating Router ID/DR Address - (4 * Number of IDs) bytes 1041 As indicated by the ID Type 1043 OSPFv2 Router IDs TLV Entry 1045 The format of the Area Router IDs TLV is: 1047 0 1 2 3 1048 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 1049 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1050 | Type | Length | 1051 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1052 | Starting Index |L| Flags | Reserved | 1053 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1054 | | 1055 +- OSPFv2 Router ID TLV Entry -+ 1056 | ... | 1058 OSPFv2 Area Router IDs TLV 1060 TLV Type: 1 1062 TLV Length: 4 + (8 * the number TLV entries) 1063 Starting index: The index of the first Router/Designated Router ID 1064 that appears in this TLV. 1066 L (Last): This bit is set if the index of the last Router/ 1067 Designated ID that appears in this TLV is equal to the last index 1068 in the full list of Rourer IDs for the area. 1070 OSPFv2 Router ID TLV Entries: A concatenated list of Router ID TLV 1071 Entries for the area. 1073 If there are multiple OSPFv2 Area Router ID TLVs with the L bit set 1074 advertised by the same router, the TLV which specifies the smaller 1075 maximum index is used and the other TLV(s) with L bit set are 1076 ignored. TLVs which specify Router IDs with indices greater than 1077 that specified by the TLV with the L bit set are also ignored. 1079 5.2.5.2. OSPFv3 Area Router ID TLV 1081 This TLV is a top level TLV of the OSPFv3 Dynamic Flooding LSA. 1083 Because the space in a single OSPFv3 Area Router ID TLV is limited, 1084 more than one TLV may be required to encode all of the Router IDs in 1085 the area. This TLV may also occur in multiple OSPFv3 Dynamic 1086 Flooding Opaque LSAs so that all Router IDs can be advertised. 1088 Each entry in the OSPFv3 Area Router IDs TLV represents either a 1089 router or a Broadcast/NBMA network identifier. An entry has the 1090 following format: 1092 0 1 2 3 1093 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 1094 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1095 | Conn Type | Number of IDs | Reserved | 1096 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1097 | | 1098 +- Originating ID Entry -+ 1099 | ... | 1101 where 1103 Conn Type - 1 byte 1104 The following values are defined: 1105 1 - Router 1106 2 - Designated Router 1108 Number of IDs - 2 bytes 1110 Reserved - 1 byte 1111 MUST be transmitted as 0 and MUST be ignored on receipt 1113 Originating ID Entry takes one of the following forms: 1115 Router: 1116 0 1 2 3 1117 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 1118 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1119 | Originating Router ID | 1120 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1122 Length of Originating ID Entry is 4 * Number of IDs) bytes 1124 Designated Router: 1125 0 1 2 3 1126 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 1127 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1128 | Originating Router ID | 1129 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1130 | Interface ID | 1131 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1133 Length of Originating ID Entry is (8 * Number of IDs) bytes 1135 OSPFv3 Router ID TLV Entry 1137 The format of the OSPFv3Area Router IDs TLV is: 1139 0 1 2 3 1140 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 1141 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1142 | Type | Length | 1143 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1144 | Starting Index |L| Flags | Reserved | 1145 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1146 | | 1147 +- OSPFv3 Router ID TLV Entry -+ 1148 | ... | 1150 OSPFv3 Area Router IDs TLV 1152 TLV Type: 1 1154 TLV Length: 4 + sum of the lengths of all TLV entries 1156 Starting index: The index of the first Router/Designated Router ID 1157 that appears in this TLV. 1159 L (Last): This bit is set if the index of the last Router/ 1160 Designated Router ID that appears in this TLV is equal to the last 1161 index in the full list of Router IDs for the area. 1163 OSPFv3 Router ID TLV Entries: A concatenated list of Router ID TLV 1164 Entries for the area. 1166 If there are multiple OSPFv3 Area Router ID TLVs with the L bit set 1167 advertised by the same router, the TLV which specifies the smaller 1168 maximum index is used and the other TLV(s) with L bit set are 1169 ignored. TLVs which specify Router IDs with indices greater than 1170 that specified by the TLV with the L bit set are also ignored. 1172 5.2.6. OSPF Flooding Path TLV 1174 The OSPF Flooding Path TLV is a top level TLV of the OSPFv2 Dynamic 1175 Flooding Opaque LSAs and OSPFv3 Dynamic Flooding LSA. 1177 The usage of the OSPF Flooding Path TLV is identical to IS-IS and is 1178 described in Section 5.1.4. 1180 The OSPF Flooding Path TLV contains a list of Router ID indices 1181 relative to the Router IDs advertised through the OSPF Area Router 1182 IDs TLV. At least 2 indices must be included in the TLV. 1184 Multiple OSPF Flooding Path TLVs can be advertised in a single OSPFv2 1185 Dynamic Flooding Opaque LSA or OSPFv3 Dynamic Flooding LSA. OSPF 1186 Flooding Path TLVs can also be advertised in multiple OSPFv2 Dynamic 1187 Flooding Opaque LSAs or OSPFv3 Dynamic Flooding LSA, if they all can 1188 not fit in a single LSA. 1190 The Flooding Path TLV has the format: 1192 0 1 2 3 1193 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 1194 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1195 | Type | Length | 1196 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1197 | Starting Index | Index 2 | 1198 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1199 | | 1200 +- Additional Indices -+ 1201 | ... | 1203 OSPF Flooding Path TLV 1205 TLV Type: 2 1207 TLV Length: 2 * (number of indices in the path) 1209 Starting index: The index of the first Router ID in the path. 1211 Index 2: The index of the next Router ID in the path. 1213 Additional indices (optional): A sequence of additional indices to 1214 Router IDs along the path. 1216 5.2.7. OSPF Flooding Request Bit 1218 A single new option bit, the Flooding-Request (FR-bit), is defined in 1219 the LLS Type 1 Extended Options and Flags field [RFC2328]. The FR- 1220 bit allows a router to request an adjacent node to enable flooding 1221 towards it on a specific link in the case where the connection to 1222 adjacent node is not part of the current flooding topology. 1224 Nodes that support Dynamic Flooding MAY include FR-bit in its OSPF 1225 LLS Extended Options and Flags TLV. 1227 If FR-bit is signalled for an area for which the flooding on the link 1228 was disabled due to Dynamic Flooding, the flooding MUST be 1229 temporarily enabled over such link and area. Flooding MUST be 1230 enabled until FR-bit is no longer advertised in the OSPF LLS Extended 1231 Options and Flags TLV or the OSPF LLS Extended Options and Flags TLV 1232 no longer appears in the OSPF Hellos. 1234 When the flooding is temporarily enabled on the link for any area due 1235 to received FR-bit in OSPF LLS Extended Options and Flags TLV, the 1236 receiver MUST perform standard database synchronization for the 1237 corresponding area(s) on the link. If the adjacency is already in 1238 the FULL state, mechanism specified in [RFC4811] MUST be used for 1239 database resynchronization. 1241 So long as the FR-bit is being received in the OSPF LLS Extended 1242 Options and Flags TLV for an area, flooding MUST NOT be disabled in 1243 such area even if the connection between the neighbors is removed 1244 from the flooding topology. Flooding for such area MUST continue on 1245 the link and be considered as temporarily enabled. 1247 5.2.8. OSPF LEEF Advertisement 1249 In support of advertising which edges are currently enabled in the 1250 flooding topology, an implementation MAY indicate that a link is part 1251 of the flooding topology. The OSPF Link Attributes Bits TLV is 1252 defined to support this advertisement. 1254 0 1 2 3 1255 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 1256 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1257 | Type | Length | 1258 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1259 | Link Attribute Bits | 1260 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1261 | | 1262 +- Additional Link Attribute Bits -+ 1263 | ... | 1265 OSPF Link Attributes Bits TLV 1267 Type: TBD and specific to OSPFv2 and OSPFv3 1269 Length: size of the Link Attribute Bits in bytes. It MUST be a 1270 multiple of 4 bytes. 1272 The following bits are defined: 1274 Bit #0: - Local Edge Enabled for Flooding (LEEF) 1276 OSPF Link-attribute Bits TLV appears as: 1278 1. a sub-TLV of the OSPFv2 Extended Link TLV [RFC7684] 1280 2. a sub-TLV of the OSPFv3 Router-Link TLV [RFC8362] 1282 6. Behavioral Specification 1284 In this section, we specify the detailed behaviors of the nodes 1285 participating in the IGP. 1287 6.1. Terminology 1289 We define some terminology here that is used in the following 1290 sections: 1292 A node is considered reachable if it is part of the connected 1293 network graph. Note that this is independent of any constraints 1294 which may be considered when performing IGP SPT calculation (e.g., 1295 link metrics, OL bit state, etc.). Two-way-connectivity check 1296 MUST be performed before including an edge in the connected 1297 network graph. 1299 Node is connected to the flooding topology, if it has at least one 1300 local link, which is part of the flooding topology. 1302 Node is disconnected from the flooding topology when it is not 1303 connected to the flooding topology. 1305 Current flooding topology - latest version of the flooding 1306 topology received (in case of the centralized mode) or calculated 1307 locally (in case of the distributed mode). 1309 6.2. Flooding Topology 1311 The flooding topology MUST include all reachable nodes in the area. 1313 If a node's reachability changes, the flooding topology MUST be 1314 recalculated. In centralized mode, the Area Leader MUST advertise a 1315 new flooding topology. 1317 If a node becomes disconnected from the current flooding topology but 1318 is still reachable then a new flooding topology MUST be calculated. 1319 In centralized mode the Area Leader MUST advertise the new flooding 1320 topology. 1322 The flooding topology SHOULD be bi-connected. 1324 6.3. Leader Election 1326 Any node that is capable MAY advertise its eligibility to become Area 1327 Leader. 1329 Nodes that are not reachable are not eligible as Area Leader. Nodes 1330 that do not advertise their eligibility to become Area Leader are not 1331 eligible. Amongst the eligible nodes, the node with the numerically 1332 highest priority is the Area Leader. If multiple nodes all have the 1333 highest priority, then the node with the numerically highest system 1334 identifier in the case of IS-IS, or Router-ID in the case of OSPFv2 1335 and OSPFv3 is the Area Leader. 1337 6.4. Area Leader Responsibilities 1339 If the Area Leader operates in centralized mode, it MUST advertise 1340 algorithm 0 in its Area Leader Sub-TLV. In order for Dynamic 1341 Flooding to be enabled it also MUST compute and advertise a flooding 1342 topology for the area. The Area Leader may update the flooding 1343 topology at any time, however, it should not destabilize the network 1344 with undue or overly frequent topology changes. If the Area Leader 1345 operates in centralized mode and needs to advertise a new flooding 1346 topology, it floods the new flooding topology on both the new and old 1347 flooding topologies. 1349 If the Area Leader operates in distributed mode, it MUST advertise a 1350 non-zero algorithm in its Area Leader Sub-TLV. 1352 When the Area Leader advertises algorithm 0 in its Area Leader Sub- 1353 TLV and does not advertise a flooding topology, Dynamic Flooding is 1354 disabled for the area. Note this applies whether the Area Leader 1355 intends to operate in centralized mode or in distributed mode. 1357 Note that once Dynamic Flooding is enabled, disabling it risks 1358 destabilizing the network. 1360 6.5. Distributed Flooding Topology Calculation 1362 If the Area Leader advertises a non-zero algorithm in its Area Leader 1363 Sub-TLV, all nodes in the area that support Dynamic Flooding and the 1364 value of algorithm advertised by the Area Leader MUST compute the 1365 flooding topology based on the Area Leader's advertised algorithm. 1367 Nodes that do not support the value of algorithm advertised by the 1368 Area Leader MUST continue to use standard flooding mechanism as 1369 defined by the protocol. 1371 Nodes that do not support the value of algorithm advertised by the 1372 Area Leader MUST be considered as Dynamic Flooding incapable nodes by 1373 the Area Leader. 1375 If the value of the algorithm advertised by the Area Leader is from 1376 the range 128-254 (private distributed algorithms), it is the 1377 responsibility of the network operator to guarantee that all nodes in 1378 the area have a common understanding of what the given algorithm 1379 value represents. 1381 6.6. Use of LANs in the Flooding Topology 1383 Use of LANs in the flooding topology differs depending on whether the 1384 area is operating in Centralized or Distributed mode. 1386 6.6.1. Use of LANs in Centralized mode 1388 As specified in Section 4.5, when a LAN is advertised as part of the 1389 flooding topology, all nodes connected to the LAN are assumed to be 1390 using the LAN as part of the flooding topology. This assumption is 1391 made to reduce the size of the Flooding Topology advertisement. 1393 6.6.2. Use of LANs in Distributed Mode 1395 In distributed mode, the flooding topology is NOT advertised, 1396 therefore the space consumed to advertise it is not a concern. It is 1397 therefore possible to assign only a subset of the nodes connected to 1398 the LAN to use the LAN as part of the flooding topology. Doing so 1399 may further optimize flooding by reducing the amount of redundant 1400 flooding on a LAN. However, support of flooding only by a subset of 1401 the nodes connected to a LAN requires some modest - but backwards 1402 compatible - changes in the way flooding is performed on a LAN. 1404 6.6.2.1. Partial flooding on a LAN in IS-IS 1406 Designated Intermediate System (DIS) for a LAN MUST use standard 1407 flooding behavior. 1409 Non-DIS nodes whose connection to the LAN is included in the flooding 1410 topology MUST use standard flooding behavior. 1412 Non-DIS nodes whose connection to the LAN is NOT included in the 1413 flooding topology behave as follows: 1415 o Received CSNPs from the DIS are ignored 1417 o PSNPs are NOT originated on the LAN 1419 o LSPs received on the LAN which are newer than the corresponding 1420 LSP present in the LSPDB are retained and flooded on all local 1421 circuits which are part of the flooding topology (i.e., do not 1422 discard newer LSPs simply because they were received on a LAN 1423 which the receiving node is not using for flooding) 1425 o LSPs received on the LAN which are older or same as the 1426 corresponding LSP present in the LSPDB are silently discarded 1428 o LSPs received on links other than the LAN are NOT flooded on the 1429 LAN 1431 NOTE: If any node connected to the LAN requests the enablement of 1432 temporary flooding all nodes revert to standard flooding behavior. 1434 6.6.2.2. Partial Flooding on a LAN in OSPF 1436 Designated Router (DR) and Backup Designated Router (BDR) for LANs 1437 MUST use standard flooding behavior. 1439 Non-DR/BDR nodes whose connection to the LAN is included in the 1440 flooding topology use standard flooding behavior. 1442 Non-DR/BDR nodes whose connection to the LAN is NOT included in the 1443 flooding topology behave as follows: 1445 o LSAs received on the LAN are acknowledged to DR/BDR 1447 o LSAs received on interfaces other than the LAN are NOT flooded on 1448 the LAN 1450 NOTE: If any node connected to the LAN requests the enablement of 1451 temporary flooding all nodes revert to standard flooding behavior. 1453 NOTE: The sending of LSA acks by nodes NOT using the LAN as part of 1454 the flooding topology eliminates the need for changes on the part of 1455 the DR/BDR - which might Include nodes which do not support the 1456 flooding optimizations. 1458 6.7. Flooding Behavior 1460 Nodes that support Dynamic Flooding MUST use the flooding topology 1461 for flooding when possible, and MUST NOT revert to standard flooding 1462 when a valid flooding topology is available. 1464 In some cases a node that supports Dynamic Flooding may need to add a 1465 local link(s) to the flooding topology temporarily, even though the 1466 link(s) is not part of the calculated flooding topology. This is 1467 termed "temporary flooding" and is discussed in Section 6.8.1. 1469 The flooding topology is calculated locally in the case of 1470 distributed mode. In centralized mode the flooding topology is 1471 advertised in the area link state database. Received link state 1472 updates, whether received on a link that is in the flooding topology 1473 or on a link that is not in the flooding topology, MUST be flooded on 1474 all links that are in the flooding topology, except for the link on 1475 which the update was received. 1477 In centralized mode, if multiple flooding topologies are present in 1478 the area link state database, the node SHOULD flood on each of these 1479 topologies. 1481 When the flooding topology changes on a node, either as a result of 1482 the local computation in distributed mode or as a result of the 1483 advertisement from the Area Leader in centralized mode, the node MUST 1484 continue to flood on both the old and new flooding topology for a 1485 limited amount of time. This is required to provide all nodes 1486 sufficient time to migrate to the new flooding topology. 1488 6.8. Treatment of Topology Events 1490 In this section, we explicitly consider a variety of different 1491 topological events in the network and how Dynamic Flooding should 1492 address them. 1494 6.8.1. Temporary Addition of Link to Flooding Topology 1496 In some cases a node that supports Dynamic Flooding may need to add a 1497 local link(s) to the flooding topology temporarily, even though the 1498 link(s) is not part of the calculated flooding topology. We refer to 1499 this as "temporary flooding" on the link. 1501 When temporary flooding is enabled on the link, the flooding needs to 1502 be enabled from both directions on the link. To achieve that, the 1503 following steps MUST be performed: 1505 Link State Database needs to be re-synchronised on the link. This 1506 is done using the standard protocol mechanisms. In the case of 1507 IS-IS, this results in setting SRM bit for all LSPs on the circuit 1508 and sending compete set of CSNPs on it. In OSPF, the mechanism 1509 specified in [RFC4811] is used. 1511 Flooding is enabled locally on the link. 1513 Flooding is requested from the neighbor using the mechanism 1514 specified in section Section 5.1.5 or Section 5.2.7. 1516 The request for temporary flooding is withdrawn on the link when all 1517 of the following conditions are met: 1519 Node itself is connected to the current flooding topology. 1521 Adjacent node is connected to the current flooding topology. 1523 Any change in the flooding topology MUST result in evaluation of the 1524 above conditions for any link on which the temporary flooding was 1525 enabled. 1527 Temporary flooding is stopped on the link when both adjacent nodes 1528 stop requesting temporary flooding on the link. 1530 6.8.2. Local Link Addition 1532 If a local link is added to the topology, the protocol will form a 1533 normal adjacency on the link and update the appropriate link state 1534 advertisements for the nodes on either end of the link. These link 1535 state updates will be flooded on the flooding topology. 1537 In centralized mode, the Area Leader, upon receiving these updates, 1538 may choose to retain the existing flooding topology or may choose to 1539 modify the flooding topology. If it elects to change the flooding 1540 topology, it will update the flooding topology in the link state 1541 database and flood it using the new flooding topology. 1543 In distributed mode, any change in the topology, including the link 1544 addition, MUST trigger the flooding topology recalculation. This is 1545 done to ensure that all nodes converge to the same flooding topology, 1546 regardless of the time of the calculation. 1548 Temporary flooding MUST be enabled on the newly added local link, if 1549 at least one of the following conditions are met: 1551 The node on which the local link was added is not connected to the 1552 current flooding topology. 1554 The new adjacent node is not connected to the current flooding 1555 topology. 1557 Note that in this case there is no need to perform a database 1558 synchronization as part of the enablement of the temporary flooding, 1559 because it has been part of the adjacency bring-up itself. 1561 If multiple local links are added to the topology before the flooding 1562 topology is updated, temporary flooding MUST be enabled on a subset 1563 of these links. 1565 6.8.3. Node Addition 1567 If a node is added to the topology, then at least one link is also 1568 added to the topology. Section 6.8.2 applies. 1570 A node which has a large number of neighbors is at risk for 1571 introducing a local flooding storm if all neighbors are brought up at 1572 once and temporary flooding is enabled on all links simultaneously. 1573 The most robust way to address this is to limit the rate of initial 1574 adjacency formation following bootup. This both reduces unnecessary 1575 redundant flooding as part of initial database synchronization and 1576 minimizes the need for temporary flooding as it allows time for the 1577 new node to be added to the flooding topology after only a small 1578 number of adjacencies have been formed. 1580 In the event a node elects to bring up a large number of adjacencies 1581 simultaneously, a significant amount of redundant flooding may be 1582 introduced as multiple neighbors of the new node enable temporary 1583 flooding to the new node which initially is not part of the flooding 1584 topology. 1586 6.8.4. Failures of Link Not on Flooding Topology 1588 If a link that is not part of the flooding topology fails, then the 1589 adjacent nodes will update their link state advertisements and flood 1590 them on the flooding topology. 1592 In centralized mode, the Area Leader, upon receiving these updates, 1593 may choose to retain the existing flooding topology or may choose to 1594 modify the flooding topology. If it elects to change the flooding 1595 topology, it will update the flooding topology in the link state 1596 database and flood it using the new flooding topology. 1598 In distributed mode, any change in the topology, including the 1599 failure of the link that is not part of the flooding topology MUST 1600 trigger the flooding topology recalculation. This is done to ensure 1601 that all nodes converge to the same flooding topology, regardless of 1602 the time of the calculation. 1604 6.8.5. Failures of Link On the Flooding Topology 1606 If there is a failure on the flooding topology, the adjacent nodes 1607 will update their link state advertisements and flood them. If the 1608 original flooding topology is bi-connected, the flooding topology 1609 should still be connected despite a single failure. 1611 If the failed local link represented the only connection to the 1612 flooding topology on the node where the link failed, the node MUST 1613 enable temporary flooding on a subset of its local links. This 1614 allows the node to send its updated link state advertisement(s) and 1615 also keep receiving link state updates from other nodes in the 1616 network before the new flooding topology is calculated and 1617 distributed (in the case of centralized mode). 1619 In centralized mode, the Area Leader will notice the change in the 1620 flooding topology, recompute the flooding topology, and flood it 1621 using the new flooding topology. 1623 In distributed mode, all nodes supporting dynamic flooding will 1624 notice the change in the topology and recompute the new flooding 1625 topology. 1627 6.8.6. Node Deletion 1629 If a node is deleted from the topology, then at least one link is 1630 also removed from the topology. Section 6.8.4 and Section 6.8.5 1631 apply. 1633 6.8.7. Local Link Addition to the Flooding Topology 1635 If the new flooding topology is received in the case of centralized 1636 mode, or calculated locally in the case of distributed mode and the 1637 local link on the node that was not part of the flooding topology has 1638 been added to the flooding topology, the node MUST: 1640 Re-synchronize the Link State Database over the link. This is 1641 done using the standard protocol mechanisms. In the case of IS- 1642 IS, this results in setting SRM bit for all LSPs on the circuit 1643 and sending a complete set of CSNPs. In OSPF, the mechanism 1644 specified in [RFC4811] is used. 1646 Make the link part of the flooding topology and start flooding 1647 over it 1649 6.8.8. Local Link Deletion from the Flooding Topology 1651 If the new flooding topology is received in the case of centralized 1652 mode, or calculated locally in the case of distributed mode and the 1653 local link on the node that was part of the flooding topology has 1654 been removed from the flooding topology, the node MUST remove the 1655 link from the flooding topology. 1657 The node MUST keep flooding on such link for a limited amount of time 1658 to allow other nodes to migrate to the new flooding topology. 1660 If the removed local link represented the only connection to the 1661 flooding topology on the node, the node MUST enable temporary 1662 flooding on a subset of its local links. This allows the node to 1663 send its updated link state advertisement(s) and also keep receiving 1664 link state updates from other nodes in the network before the new 1665 flooding topology is calculated and distributed (in the case of 1666 centralized mode). 1668 6.8.9. Treatment of Disconnected Adjacent Nodes 1670 Every time there is a change in the flooding topology a node MUST 1671 check if there are any adjacent nodes that are disconnected from the 1672 current flooding topology. Temporary flooding MUST be enabled 1673 towards a subset of the disconnected nodes. 1675 6.8.10. Failure of the Area Leader 1677 The failure of the Area Leader can be detected by observing that it 1678 is no longer reachable. In this case, the Area Leader election 1679 process is repeated and a new Area Leader is elected. 1681 In order to minimize disruption to Dynamic Flooding if the Area 1682 Leader becomes unreachable, the node which has the second highest 1683 priority for becoming Area Leader (including the system identifier/ 1684 Router-ID tie breaker if necessary) SHOULD advertise the same 1685 algorithm in its Area Leader Sub-TLV as the Area Leader and (in 1686 centralized mode) SHOULD advertise a flooding topology. This SHOULD 1687 be done even when the Area Leader is reachable. 1689 In centralized mode, the new Area Leader will compute a new flooding 1690 topology and flood it using the new flooding topology. To minimze 1691 disruption, the new flooding topology SHOULD have as much in common 1692 as possible with the old flooding topology. This will minimize the 1693 risk of over-flooding. 1695 In the distributed mode, the new flooding topology will be calculated 1696 on all nodes that support the algorithm that is advertised by the new 1697 Area Leader. Nodes that do not support the algorithm advertised by 1698 the new Area Leader will no longer participate in Dynamic Flooding 1699 and will revert to standard flooding. 1701 6.8.11. Recovery from Multiple Failures 1703 In the unlikely event of multiple failures on the flooding topology, 1704 it may become partitioned. The nodes that remain active on the edges 1705 of the flooding topology partitions will recognize this and will try 1706 to repair the flooding topology locally by enabling temporary 1707 flooding towards the nodes that they consider disconnected from the 1708 flooding topology until a new flooding topology becomes connected 1709 again. 1711 Nodes where local failure was detected update their own link state 1712 advertisements and flood them on the remainder of the flooding 1713 topology. 1715 In centralized mode, the Area Leader will notice the change in the 1716 flooding topology, recompute the flooding topology, and flood it 1717 using the new flooding topology. 1719 In distributed mode, all nodes that actively participate in Dynamic 1720 Flooding will compute the new flooding topology. 1722 Note that this is very different from the area partition because 1723 there is still a connected network graph between the nodes in the 1724 area. The area may remain connected and forwarding may still be 1725 effective. 1727 6.8.12. Rate Limiting Temporary Flooding 1729 As discussed in the previous sections, there are events which require 1730 the introduction of temporary flooding on edges which are not part of 1731 the current flooding topology. This can occur regardless of whether 1732 the area is operating in centralized mode or distributed mode. 1734 Nodes which decide to enable temporary flooding also have to decide 1735 whether to do so on a subset of the edges which are currently not 1736 part of the flooding topology or on all the edges which are currently 1737 not part of the flooding topology. Doing the former risks a longer 1738 convergence time as it is possible that the initial set of edges 1739 enabled does not fully repair the flooding topology. Doing the 1740 latter risks introducing a flooding storm which destablizes the 1741 network. 1743 It is recommended that a node implement rate limiting on the number 1744 of edges on which it chooses to enable temporary flooding. Initial 1745 values for the number of edges to enable and the rate at which 1746 additional edges may subsequently be enabled is left as an 1747 implementation decision. 1749 7. IANA Considerations 1751 7.1. IS-IS 1753 This document requests the following code points from the "sub-TLVs 1754 for TLV 242" registry (IS-IS Router CAPABILITY TLV). 1756 Type: TBD1 1758 Description: IS-IS Area Leader Sub-TLV 1760 Reference: This document (Section 5.1.1) 1762 Type: TBD7 1764 Description: IS-IS Dynamic Flooding Sub-TLV 1766 Reference: This document (Section 5.1.2) 1768 This document requests that IANA allocate and assign code points from 1769 the "IS-IS TLV Codepoints" registry. One for each of the following 1770 TLVs: 1772 Type: TBD2 1774 Description: IS-IS Area System IDs TLV 1776 Reference: This document (Section 5.1.3) 1778 Type: TBD3 1780 Description: IS-IS Flooding Path TLV 1782 Reference: This document (Section 5.1.4) 1784 Type: TBD9 1786 Description: IS-IS Flooding Request TLV 1788 Reference: This document (Section 5.1.5) 1790 This document requests that IANA allocate a new bit value from the 1791 "link-attribute bit values for sub-TLV 19 of TLV 22" registry. 1793 Local Edge Enabled for Flooding (LEEF) - suggested value 4 (to be 1794 assigned by IANA) 1796 7.2. OSPF 1798 This document requests the following code points from the "OSPF 1799 Router Information (RI) TLVs" registry: 1801 Type: TBD4 1803 Description: OSPF Area Leader Sub-TLV 1804 Reference: This document (Section 5.2.1) 1806 Type: TBD8 1808 Description: OSPF Dynamic Flooding Sub-TLV 1810 Reference: This document (Section 5.2.2) 1812 This document requests the following code point from the "Opaque 1813 Link-State Advertisements (LSA) Option Types" registry: 1815 Type: TBD5 1817 Description: OSPFv2 Dynamic Flooding Opaque LSA 1819 Reference: This document (Section 5.2.3) 1821 This document requests the following code point from the "OSPFv3 LSA 1822 Function Codes" registry: 1824 Type: TBD6 1826 Description: OSPFv3 Dynamic Flooding LSA 1828 Reference: This document (Section 5.2.4) 1830 This document requests a new bit in LLS Type 1 Extended Options and 1831 Flags registry: 1833 Bit Position: TBD10 1835 Description: Flooding Request bit 1837 Reference: This document (Section 5.2.7) 1839 This document requests the following code point from the "OSPFv2 1840 Extended Link TLV Sub-TLVs" registry: 1842 Type: TBD11 1844 Description: OSPFv2 Link Attributes Bits Sub-TLV 1846 Reference: This document (Section 5.2.8) 1848 This document requests the following code point from the "OSPFv3 1849 Extended LSA Sub-TLVs" registry: 1851 Type: TBD12 1852 Description: OSPFv3 Link Attributes Bits Sub-TLV 1854 Reference: This document (Section 5.2.8) 1856 7.2.1. OSPF Dynamic Flooding LSA TLVs Registry 1858 This specification also requests a new registry - "OSPF Dynamic 1859 Flooding LSA TLVs". New values can be allocated via IETF Review or 1860 IESG Approval 1862 The "OSPF Dynamic Flooding LSA TLVs" registry will define top-level 1863 TLVs for the OSPFv2 Dynamic Flooding Opaque LSA and OSPFv3 Dynamic 1864 Flooding LSAs. It should be added to the "Open Shortest Path First 1865 (OSPF) Parameters" registries group. 1867 The following initial values are allocated: 1869 Type: 0 1871 Description: Reserved 1873 Reference: This document 1875 Type: 1 1877 Description: OSPF Area Router IDs TLV 1879 Reference: This document (Section 5.2.5) 1881 Type: 2 1883 Description: OSPF Flooding Path TLV 1885 Reference: This document (Section 5.2.6) 1887 Types in the range 32768-33023 are for experimental use; these will 1888 not be registered with IANA, and MUST NOT be mentioned by RFCs. 1890 Types in the range 33024-65535 are not to be assigned at this time. 1891 Before any assignments can be made in the 33024-65535 range, there 1892 MUST be an IETF specification that specifies IANA Considerations that 1893 covers the range being assigned. 1895 7.2.2. OSPF Link Attributes Sub-TLV Bit Values Registry 1897 This specification also requests a new registry - "OSPF Link 1898 Attributes Sub-TLV Bit Values". New values can be allocated via IETF 1899 Review or IESG Approval 1900 The "OSPF Link Attributes Sub-TLV Bit Values" registry defines Link 1901 Attribute bit values for the OSPFv2 Link Attributes Sub-TLV and 1902 OSPFv3 Link Attributes Sub-TLV. It should be added to the "Open 1903 Shortest Path First (OSPF) Parameters" registries group. 1905 The following initial value is allocated: 1907 Bit Number: 0 1909 Description: Local Edge Enabled for Flooding(LEEF) 1911 Reference: This document (Section 5.2.8) 1913 7.3. IGP 1915 IANA is requested to set up a registry called "IGP Algorithm Type For 1916 Computing Flooding Topology" under an existing "Interior Gateway 1917 Protocol (IGP) Parameters" IANA registries. 1919 Values in this registry come from the range 0-255. 1921 The initial values in the IGP Algorithm Type For Computing Flooding 1922 Topology registry are: 1924 0: Reserved for centralized mode. Individual values are are to be 1925 assigned according to the "Specification Required" policy defined 1926 in [RFC8126] 1928 1-127: Available for standards action.Individual values are are to 1929 be assigned according to the "Private Use" policy defined in 1930 [RFC8126] 1932 128-254: Reserved for private use. 1934 255: Reserved. 1936 8. Security Considerations 1938 This document introduces no new security issues. Security of routing 1939 within a domain is already addressed as part of the routing protocols 1940 themselves. This document proposes no changes to those security 1941 architectures. 1943 It is possible that an attacker could become Area Leader and 1944 introduce a flawed flooding algorithm into the network thus 1945 compromising the operation of the protocol. Authentication methods 1946 as describe in [RFC5304] and [RFC5310] for IS-IS, [RFC2328] and 1948 [RFC7474] for OSPFv2 and [RFC5340] and [RFC4552] for OSPFv3 SHOULD be 1949 used to prevent such attack. 1951 9. Acknowledgements 1953 The authors would like to thank Sarah Chen for her contribution to 1954 this work. 1956 The authors would like to thank Zeqing (Fred) Xia, Naiming Shen, Adam 1957 Sweeney and Olufemi Komolafe for their helpful comments. 1959 The authors would like to thank Tom Edsall for initially introducing 1960 them to the problem. 1962 Advertising Local Edges Enabled for Flooding (LEEF) is based on an 1963 idea proposed in [I-D.cc-lsr-flooding-reduction]. We wish to thank 1964 the authors of that draft - in particular Huaimo Chen. 1966 10. References 1968 10.1. Normative References 1970 [ISO10589] 1971 International Organization for Standardization, 1972 "Intermediate System to Intermediate System Intra-Domain 1973 Routing Exchange Protocol for use in Conjunction with the 1974 Protocol for Providing the Connectionless-mode Network 1975 Service (ISO 8473)", ISO/IEC 10589:2002, Nov. 2002. 1977 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1978 Requirement Levels", BCP 14, RFC 2119, 1979 DOI 10.17487/RFC2119, March 1997, 1980 . 1982 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 1983 DOI 10.17487/RFC2328, April 1998, 1984 . 1986 [RFC4552] Gupta, M. and N. Melam, "Authentication/Confidentiality 1987 for OSPFv3", RFC 4552, DOI 10.17487/RFC4552, June 2006, 1988 . 1990 [RFC5029] Vasseur, JP. and S. Previdi, "Definition of an IS-IS Link 1991 Attribute Sub-TLV", RFC 5029, DOI 10.17487/RFC5029, 1992 September 2007, . 1994 [RFC5250] Berger, L., Bryskin, I., Zinin, A., and R. Coltun, "The 1995 OSPF Opaque LSA Option", RFC 5250, DOI 10.17487/RFC5250, 1996 July 2008, . 1998 [RFC5304] Li, T. and R. Atkinson, "IS-IS Cryptographic 1999 Authentication", RFC 5304, DOI 10.17487/RFC5304, October 2000 2008, . 2002 [RFC5310] Bhatia, M., Manral, V., Li, T., Atkinson, R., White, R., 2003 and M. Fanto, "IS-IS Generic Cryptographic 2004 Authentication", RFC 5310, DOI 10.17487/RFC5310, February 2005 2009, . 2007 [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF 2008 for IPv6", RFC 5340, DOI 10.17487/RFC5340, July 2008, 2009 . 2011 [RFC5613] Zinin, A., Roy, A., Nguyen, L., Friedman, B., and D. 2012 Yeung, "OSPF Link-Local Signaling", RFC 5613, 2013 DOI 10.17487/RFC5613, August 2009, 2014 . 2016 [RFC7120] Cotton, M., "Early IANA Allocation of Standards Track Code 2017 Points", BCP 100, RFC 7120, DOI 10.17487/RFC7120, January 2018 2014, . 2020 [RFC7356] Ginsberg, L., Previdi, S., and Y. Yang, "IS-IS Flooding 2021 Scope Link State PDUs (LSPs)", RFC 7356, 2022 DOI 10.17487/RFC7356, September 2014, 2023 . 2025 [RFC7474] Bhatia, M., Hartman, S., Zhang, D., and A. Lindem, Ed., 2026 "Security Extension for OSPFv2 When Using Manual Key 2027 Management", RFC 7474, DOI 10.17487/RFC7474, April 2015, 2028 . 2030 [RFC7684] Psenak, P., Gredler, H., Shakir, R., Henderickx, W., 2031 Tantsura, J., and A. Lindem, "OSPFv2 Prefix/Link Attribute 2032 Advertisement", RFC 7684, DOI 10.17487/RFC7684, November 2033 2015, . 2035 [RFC7770] Lindem, A., Ed., Shen, N., Vasseur, JP., Aggarwal, R., and 2036 S. Shaffer, "Extensions to OSPF for Advertising Optional 2037 Router Capabilities", RFC 7770, DOI 10.17487/RFC7770, 2038 February 2016, . 2040 [RFC7981] Ginsberg, L., Previdi, S., and M. Chen, "IS-IS Extensions 2041 for Advertising Router Information", RFC 7981, 2042 DOI 10.17487/RFC7981, October 2016, 2043 . 2045 [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for 2046 Writing an IANA Considerations Section in RFCs", BCP 26, 2047 RFC 8126, DOI 10.17487/RFC8126, June 2017, 2048 . 2050 [RFC8362] Lindem, A., Roy, A., Goethals, D., Reddy Vallem, V., and 2051 F. Baker, "OSPFv3 Link State Advertisement (LSA) 2052 Extensibility", RFC 8362, DOI 10.17487/RFC8362, April 2053 2018, . 2055 10.2. Informative References 2057 [Clos] Clos, C., "A Study of Non-Blocking Switching Networks", 2058 The Bell System Technical Journal Vol. 32(2), DOI 2059 10.1002/j.1538-7305.1953.tb01433.x, March 1953, 2060 . 2062 [I-D.cc-lsr-flooding-reduction] 2063 Chen, H., Cheng, D., Toy, M., Yang, Y., Wang, A., Liu, X., 2064 Fan, Y., and L. Liu, "LS Distributed Flooding Reduction", 2065 draft-cc-lsr-flooding-reduction-03 (work in progress), 2066 March 2019. 2068 [Leiserson] 2069 Leiserson, C., "Fat-Trees: Universal Networks for 2070 Hardware-Efficient Supercomputing", IEEE Transactions on 2071 Computers 34(10):892-901, 1985. 2073 [RFC2973] Balay, R., Katz, D., and J. Parker, "IS-IS Mesh Groups", 2074 RFC 2973, DOI 10.17487/RFC2973, October 2000, 2075 . 2077 [RFC3630] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering 2078 (TE) Extensions to OSPF Version 2", RFC 3630, 2079 DOI 10.17487/RFC3630, September 2003, 2080 . 2082 [RFC4811] Nguyen, L., Roy, A., and A. Zinin, "OSPF Out-of-Band Link 2083 State Database (LSDB) Resynchronization", RFC 4811, 2084 DOI 10.17487/RFC4811, March 2007, 2085 . 2087 [RFC7938] Lapukhov, P., Premji, A., and J. Mitchell, Ed., "Use of 2088 BGP for Routing in Large-Scale Data Centers", RFC 7938, 2089 DOI 10.17487/RFC7938, August 2016, 2090 . 2092 Authors' Addresses 2094 Tony Li (editor) 2095 Arista Networks 2096 5453 Great America Parkway 2097 Santa Clara, California 95054 2098 USA 2100 Email: tony.li@tony.li 2102 Peter Psenak (editor) 2103 Cisco Systems, Inc. 2104 Eurovea Centre, Central 3 2105 Pribinova Street 10 2106 Bratislava 81109 2107 Slovakia 2109 Email: ppsenak@cisco.com 2111 Les Ginsberg 2112 Cisco Systems, Inc. 2113 510 McCarthy Blvd. 2114 Milpitas, California 95035 2115 USA 2117 Email: ginsberg@cisco.com 2119 Tony Przygienda 2120 Juniper Networks, Inc. 2121 1194 N. Mathilda Ave 2122 Sunnyvale, California 94089 2123 USA 2125 Email: prz@juniper.net 2126 Dave Cooper 2127 CenturyLink 2128 1025 Eldorado Blvd 2129 Broomfield, Colorado 80021 2130 USA 2132 Email: Dave.Cooper@centurylink.com 2134 Luay Jalil 2135 Verizon 2136 Richardson, Texas 75081 2137 USA 2139 Email: luay.jalil@verizon.com 2141 Srinath Dontula 2142 ATT 2143 200 S Laurel Ave 2144 Middletown, New Jersey 07748 2145 USA 2147 Email: sd947e@att.com