--- 1/draft-ietf-lsr-dynamic-flooding-01.txt 2019-05-27 20:13:09.604401924 -0700 +++ 2/draft-ietf-lsr-dynamic-flooding-02.txt 2019-05-27 20:13:09.696404251 -0700 @@ -1,28 +1,28 @@ Internet Engineering Task Force T. Li, Ed. Internet-Draft Arista Networks Intended status: Standards Track P. Psenak, Ed. -Expires: November 22, 2019 L. Ginsberg +Expires: November 28, 2019 L. Ginsberg Cisco Systems, Inc. T. Przygienda Juniper Networks, Inc. D. Cooper CenturyLink L. Jalil Verizon S. Dontula ATT - May 21, 2019 + May 27, 2019 Dynamic Flooding on Dense Graphs - draft-ietf-lsr-dynamic-flooding-01 + draft-ietf-lsr-dynamic-flooding-02 Abstract Routing with link state protocols in dense network topologies can result in sub-optimal convergence times due to the overhead associated with flooding. This can be addressed by decreasing the flooding topology so that it is less dense. This document discusses the problem in some depth and an architectural solution. Specific protocol changes for IS-IS, OSPFv2, @@ -36,21 +36,21 @@ Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." - This Internet-Draft will expire on November 22, 2019. + This Internet-Draft will expire on November 28, 2019. Copyright Notice Copyright (c) 2019 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents @@ -88,57 +88,57 @@ 5.2.1. OSPF Area Leader Sub-TLV . . . . . . . . . . . . . . 18 5.2.2. OSPF Dynamic Flooding Sub-TLV . . . . . . . . . . . . 19 5.2.3. OSPFv2 Dynamic Flooding Opaque LSA . . . . . . . . . 19 5.2.4. OSPFv3 Dynamic Flooding LSA . . . . . . . . . . . . . 21 5.2.5. OSPF Area Router ID TLVs . . . . . . . . . . . . . . 22 5.2.5.1. OSPFv2 Area Router ID TLV . . . . . . . . . . . . 22 5.2.5.2. OSPFv3 Area Router ID TLV . . . . . . . . . . . . 24 5.2.6. OSPF Flooding Path TLV . . . . . . . . . . . . . . . 26 5.2.7. OSPF Flooding Request Bit . . . . . . . . . . . . . . 27 5.2.8. OSPF LEEF Advertisement . . . . . . . . . . . . . . . 28 - 6. Behavioral Specification . . . . . . . . . . . . . . . . . . 28 + 6. Behavioral Specification . . . . . . . . . . . . . . . . . . 29 6.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 29 6.2. Flooding Topology . . . . . . . . . . . . . . . . . . . . 29 6.3. Leader Election . . . . . . . . . . . . . . . . . . . . . 29 6.4. Area Leader Responsibilities . . . . . . . . . . . . . . 30 6.5. Distributed Flooding Topology Calculation . . . . . . . . 30 - 6.6. Use of LANs in the Flooding Topology . . . . . . . . . . 30 - 6.6.1. Use of LANs in Centralized mode . . . . . . . . . . . 30 + 6.6. Use of LANs in the Flooding Topology . . . . . . . . . . 31 + 6.6.1. Use of LANs in Centralized mode . . . . . . . . . . . 31 6.6.2. Use of LANs in Distributed Mode . . . . . . . . . . . 31 6.6.2.1. Partial flooding on a LAN in IS-IS . . . . . . . 31 - 6.6.2.2. Partial Flooding on a LAN in OSPF . . . . . . . . 31 + 6.6.2.2. Partial Flooding on a LAN in OSPF . . . . . . . . 32 6.7. Flooding Behavior . . . . . . . . . . . . . . . . . . . . 32 6.8. Treatment of Topology Events . . . . . . . . . . . . . . 33 6.8.1. Temporary Addition of Link to Flooding Topology . . . 33 - 6.8.2. Local Link Addition . . . . . . . . . . . . . . . . . 33 - 6.8.3. Node Addition . . . . . . . . . . . . . . . . . . . . 34 + 6.8.2. Local Link Addition . . . . . . . . . . . . . . . . . 34 + 6.8.3. Node Addition . . . . . . . . . . . . . . . . . . . . 35 6.8.4. Failures of Link Not on Flooding Topology . . . . . . 35 6.8.5. Failures of Link On the Flooding Topology . . . . . . 35 - 6.8.6. Node Deletion . . . . . . . . . . . . . . . . . . . . 35 + 6.8.6. Node Deletion . . . . . . . . . . . . . . . . . . . . 36 6.8.7. Local Link Addition to the Flooding Topology . . . . 36 6.8.8. Local Link Deletion from the Flooding Topology . . . 36 - 6.8.9. Treatment of Disconnected Adjacent Nodes . . . . . . 36 - 6.8.10. Failure of the Area Leader . . . . . . . . . . . . . 36 + 6.8.9. Treatment of Disconnected Adjacent Nodes . . . . . . 37 + 6.8.10. Failure of the Area Leader . . . . . . . . . . . . . 37 6.8.11. Recovery from Multiple Failures . . . . . . . . . . . 37 - 6.8.12. Rate Limiting Temporary Flooding . . . . . . . . . . 37 + 6.8.12. Rate Limiting Temporary Flooding . . . . . . . . . . 38 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 38 7.1. IS-IS . . . . . . . . . . . . . . . . . . . . . . . . . . 38 7.2. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . 39 - 7.2.1. OSPF Dynamic Flooding LSA TLVs Registry . . . . . . . 40 + 7.2.1. OSPF Dynamic Flooding LSA TLVs Registry . . . . . . . 41 7.2.2. OSPF Link Attributes Sub-TLV Bit Values Registry . . 41 - 7.3. IGP . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 + 7.3. IGP . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 8. Security Considerations . . . . . . . . . . . . . . . . . . . 42 - 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 42 - 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 42 - 10.1. Normative References . . . . . . . . . . . . . . . . . . 42 - 10.2. Informative References . . . . . . . . . . . . . . . . . 44 - Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 45 + 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 43 + 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 43 + 10.1. Normative References . . . . . . . . . . . . . . . . . . 43 + 10.2. Informative References . . . . . . . . . . . . . . . . . 45 + Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 46 1. Introduction In recent years, there has been increased focus on how to address the dynamic routing of networks that have a bipartite (a.k.a. spine-leaf or leaf-spine), Clos [Clos], or Fat Tree [Leiserson] topology. Conventional Interior Gateway Protocols (IGPs, i.e., IS-IS [ISO10589], OSPFv2 [RFC2328], and OSPFv3 [RFC5340]) under-perform, redundantly flooding information throughout the dense topology, leading to overloaded control plane inputs and thereby creating @@ -1012,36 +1012,39 @@ the area. This TLV may also occur in multiple OSPFv2 Dynamic Flooding Opaque LSAs so that all Router IDs can be advertised. Each entry in the OSPFv2 Area Router IDs TLV represents either a node or a Broadcast/NBMA network identifier. An entry has the following format: 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - | Conn Type | Reserved | - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - | Originating Router ID/DR Address | + | Conn Type | Number of IDs | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | + +- Originating Router ID/DR Address -+ + | ... | where Conn Type - 1 byte The following values are defined: 1 - Router 2 - Designated Router - Reserved - 3 bytes + Number of IDs - 2 bytes + + Reserved - 1 byte MUST be transmitted as 0 and MUST be ignored on receipt - Originating Router ID/DR Address - 4 bytes + Originating Router ID/DR Address - (4 * Number of IDs) bytes As indicated by the ID Type OSPFv2 Router IDs TLV Entry The format of the Area Router IDs TLV is: 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | @@ -1050,27 +1053,26 @@ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | +- OSPFv2 Router ID TLV Entry -+ | ... | OSPFv2 Area Router IDs TLV TLV Type: 1 TLV Length: 4 + (8 * the number TLV entries) + Starting index: The index of the first Router/Designated Router ID + that appears in this TLV. - Starting index: The index of the first Router ID that appears in - this TLV. - - L (Last): This bit is set if the index of the last system ID that - appears in this TLV is equal to the last index in the full list of - Rourer IDs for the area. + L (Last): This bit is set if the index of the last Router/ + Designated ID that appears in this TLV is equal to the last index + in the full list of Rourer IDs for the area. OSPFv2 Router ID TLV Entries: A concatenated list of Router ID TLV Entries for the area. If there are multiple OSPFv2 Area Router ID TLVs with the L bit set advertised by the same router, the TLV which specifies the smaller maximum index is used and the other TLV(s) with L bit set are ignored. TLVs which specify Router IDs with indices greater than that specified by the TLV with the L bit set are also ignored. @@ -1083,43 +1085,59 @@ the area. This TLV may also occur in multiple OSPFv3 Dynamic Flooding Opaque LSAs so that all Router IDs can be advertised. Each entry in the OSPFv3 Area Router IDs TLV represents either a router or a Broadcast/NBMA network identifier. An entry has the following format: 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - | Conn Type | Reserved | - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - | Originating Router ID (always present) | - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - | Interface ID (present for DRs) | + | Conn Type | Number of IDs | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | + +- Originating ID Entry -+ + | ... | where Conn Type - 1 byte The following values are defined: 1 - Router 2 - Designated Router - Reserved - 3 bytes + Number of IDs - 2 bytes + + Reserved - 1 byte MUST be transmitted as 0 and MUST be ignored on receipt - Originating Router ID - 4 bytes + Originating ID Entry takes one of the following forms: - Interface ID - 4 bytes - This field MUST be present when Conn Type indicates Designated - Router. - This field MUST NOT be present when Conn Type indicates Router. + Router: + 0 1 2 3 + 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 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Originating Router ID | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Length of Originating ID Entry is 4 * Number of IDs) bytes + + Designated Router: + 0 1 2 3 + 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 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Originating Router ID | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Interface ID | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Length of Originating ID Entry is (8 * Number of IDs) bytes OSPFv3 Router ID TLV Entry The format of the OSPFv3Area Router IDs TLV is: 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ @@ -1125,30 +1143,31 @@ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Starting Index |L| Flags | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | +- OSPFv3 Router ID TLV Entry -+ | ... | OSPFv3 Area Router IDs TLV TLV Type: 1 + TLV Length: 4 + sum of the lengths of all TLV entries - Starting index: The index of the first Router ID that appears in - this TLV. + Starting index: The index of the first Router/Designated Router ID + that appears in this TLV. - L (Last): This bit is set if the index of the last router ID that - appears in this TLV is equal to the last index in the full list of - Router IDs for the area. + L (Last): This bit is set if the index of the last Router/ + Designated Router ID that appears in this TLV is equal to the last + index in the full list of Router IDs for the area. - OSPFv2 Router ID TLV Entries: A concatenated list of Router ID TLV + OSPFv3 Router ID TLV Entries: A concatenated list of Router ID TLV Entries for the area. If there are multiple OSPFv3 Area Router ID TLVs with the L bit set advertised by the same router, the TLV which specifies the smaller maximum index is used and the other TLV(s) with L bit set are ignored. TLVs which specify Router IDs with indices greater than that specified by the TLV with the L bit set are also ignored. 5.2.6. OSPF Flooding Path TLV @@ -1311,29 +1330,39 @@ that do not advertise their eligibility to become Area Leader are not eligible. Amongst the eligible nodes, the node with the numerically highest priority is the Area Leader. If multiple nodes all have the highest priority, then the node with the numerically highest system identifier in the case of IS-IS, or Router-ID in the case of OSPFv2 and OSPFv3 is the Area Leader. 6.4. Area Leader Responsibilities If the Area Leader operates in centralized mode, it MUST advertise - algorithm 0 in its Area Leader Sub-TLV. It also MUST compute and - advertise a flooding topology for the area. The Area Leader may - update the flooding topology at any time, however, it should not - destabilize the network with undue or overly frequent topology - changes. + algorithm 0 in its Area Leader Sub-TLV. In order for Dynamic + Flooding to be enabled it also MUST compute and advertise a flooding + topology for the area. The Area Leader may update the flooding + topology at any time, however, it should not destabilize the network + with undue or overly frequent topology changes. If the Area Leader + operates in centralized mode and needs to advertise a new flooding + topology, it floods the new flooding topology on both the new and old + flooding topologies. - If the Area Leader operates in centralized mode and needs to - advertises a new flooding topology, it floods a new flooding topology - on both the new and old flooding topologies. + If the Area Leader operates in distributed mode, it MUST advertise a + non-zero algorithm in its Area Leader Sub-TLV. + + When the Area Leader advertises algorithm 0 in its Area Leader Sub- + TLV and does not advertise a flooding topology, Dynamic Flooding is + disabled for the area. Note this applies whether the Area Leader + intends to operate in centralized mode or in distributed mode. + + Note that once Dynamic Flooding is enabled, disabling it risks + destabilizing the network. 6.5. Distributed Flooding Topology Calculation If the Area Leader advertises a non-zero algorithm in its Area Leader Sub-TLV, all nodes in the area that support Dynamic Flooding and the value of algorithm advertised by the Area Leader MUST compute the flooding topology based on the Area Leader's advertised algorithm. Nodes that do not support the value of algorithm advertised by the Area Leader MUST continue to use standard flooding mechanism as @@ -1368,21 +1397,21 @@ therefore possible to assign only a subset of the nodes connected to the LAN to use the LAN as part of the flooding topology. Doing so may further optimize flooding by reducing the amount of redundant flooding on a LAN. However, support of flooding only by a subset of the nodes connected to a LAN requires some modest - but backwards compatible - changes in the way flooding is performed on a LAN. 6.6.2.1. Partial flooding on a LAN in IS-IS Designated Intermediate System (DIS) for a LAN MUST use standard - flooding behavior: + flooding behavior. Non-DIS nodes whose connection to the LAN is included in the flooding topology MUST use standard flooding behavior. Non-DIS nodes whose connection to the LAN is NOT included in the flooding topology behave as follows: o Received CSNPs from the DIS are ignored o PSNPs are NOT originated on the LAN @@ -1642,25 +1671,31 @@ check if there are any adjacent nodes that are disconnected from the current flooding topology. Temporary flooding MUST be enabled towards a subset of the disconnected nodes. 6.8.10. Failure of the Area Leader The failure of the Area Leader can be detected by observing that it is no longer reachable. In this case, the Area Leader election process is repeated and a new Area Leader is elected. - In the centralized mode, the new Area Leader will compute a new - flooding topology and flood it using the new flooding topology. + In order to minimize disruption to Dynamic Flooding if the Area + Leader becomes unreachable, the node which has the second highest + priority for becoming Area Leader (including the system identifier/ + Router-ID tie breaker if necessary) SHOULD advertise the same + algorithm in its Area Leader Sub-TLV as the Area Leader and (in + centralized mode) SHOULD advertise a flooding topology. This SHOULD + be done even when the Area Leader is reachable. - As an optimization, applicable to centralized mode, the new Area - Leader MAY compute a new flooding topology that has as much in common + In centralized mode, the new Area Leader will compute a new flooding + topology and flood it using the new flooding topology. To minimze + disruption, the new flooding topology SHOULD have as much in common as possible with the old flooding topology. This will minimize the risk of over-flooding. In the distributed mode, the new flooding topology will be calculated on all nodes that support the algorithm that is advertised by the new Area Leader. Nodes that do not support the algorithm advertised by the new Area Leader will no longer participate in Dynamic Flooding and will revert to standard flooding. 6.8.11. Recovery from Multiple Failures