Network Working Group T. Przygienda Internet-Draft S. Hegde Intended status: Standards Track Juniper Networks Expires: 17 July 2025 13 January 2025 Flooding Reduction Algorithms Interoperability Framework draft-lsr-interop-flood-reduction-architecture-00 Abstract This document introduces a framework that makes it possible to deploy multiple flood reduction algorithms within the same IGP domain in an interoperable fashion. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. 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 17 July 2025. Copyright Notice Copyright (c) 2025 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 carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Przygienda & Hegde Expires 17 July 2025 [Page 1] Internet-Draft Flooding Reduction Algorithms Interopera January 2025 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Flooding Prunner Framework . . . . . . . . . . . . . . . . . 2 2.1. Definitions and Axioms . . . . . . . . . . . . . . . . . 2 2.1.1. Maximum of One Flooding Prunner on a Node . . . . . . 3 2.1.2. Connected Component . . . . . . . . . . . . . . . . . 3 2.1.3. Flooding Connected Dominating Sets . . . . . . . . . 3 2.1.4. Flooding Prunner . . . . . . . . . . . . . . . . . . 4 2.2. Desirable Properties of the Flooding Prunner Framework . 5 2.3. Example . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4. Signalling . . . . . . . . . . . . . . . . . . . . . . . 7 3. Security Considerations . . . . . . . . . . . . . . . . . . . 7 4. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 7 5. Normative References . . . . . . . . . . . . . . . . . . . . 7 6. Informative References . . . . . . . . . . . . . . . . . . . 8 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 8 1. Introduction Scenarios exist where multiple distributed (or centralized) flood reduction algorithms may be deployed simultaneously within an IGP domain. These scenarios necessitate certain co-operative behaviors between the involved algorithms to ensure the correctness of the overall solution. This is true in both permanent and transient (i.e., migration) deployment cases. Fortunately, existing graph theory concepts allow us to provide guidance towards design of algorithms with the necessary properties to ensure their interoperable co-existence. This document presents the necessary requirements for the involved algorithms and the details of a framework for their interoperable deployment. Though running multiple algorithms simultaneously may not be a preferred operational choice, it is necessary if the migration from one algorithm to another while ensuring minimal network disruption is a priority. A migration itself may be caused by discovery of defects in deployed algorithms or deployment of new algorithms offering improvements. 2. Flooding Prunner Framework 2.1. Definitions and Axioms This section will outline a framework allowing the operation of multiple different flood reduction algorithms (called "flooding pruners" or "pruners" from here on) in an interoperable fashion. Przygienda & Hegde Expires 17 July 2025 [Page 2] Internet-Draft Flooding Reduction Algorithms Interopera January 2025 As first important observation upfront, it will become clear later in this section that full, non-optimized flooding presents a special case of a pruner itself. Normal flooding is including all adjacencies without any prunning and hence we name it the "zero- pruner" or "zero" for short. 2.1.1. Maximum of One Flooding Prunner on a Node This framework permits maximum of a single active pruner on each node. It allows to change a specific pruner at any time on any subset of nodes in the network while limiting the impact to the node itself and possibly the re-convergence of a set of nodes within its component. 2.1.2. Connected Component A connected component (or component for short) is defined as subset of nodes running the same pruner (denoted as A) where each of the nodes can be connected to all other nodes by a path that traverses only nodes that run A. Observe that there well may be in the network multiple components which are not connected, but run the same pruner. We denote a component for pruner P as P| and if two disjoint components running P are present in the network as P|' and P|''. Observe that zero-pruner also builds components denoted as Z| and its primes. Another way to visualize components is to consider a network running multiple pruners as "islands running non-zero algorithms" that are connected to each other via components running zero pruner (i.e. using normal flooding). 2.1.3. Flooding Connected Dominating Sets A pruner may choose within its component a subset of links to flood while making sure that the component remains connected. In other words, after suppressing flooding on some links within the component there must still exist paths consisting of the remaining links that connect each pair of nodes in the component. We use for those remaining links the term flooding connected dominating set or CDS for short (more precisely, an edge dominating set which is not necessarily loop-free). Such a CDS is colloquially often called "flooding topology" in context of flood reduction algorithms. A simple spanning tree is an easily visualized special case of a CDS. We denote such a CDS for a component A| as A|*. Observe that A|* is not unique for a component (i.e. many different sets of links can be a CDS). Nor is it required that a CDS has to be loop-free (i.e. there may be many different paths on the CDS between two nodes in a Przygienda & Hegde Expires 17 July 2025 [Page 3] Internet-Draft Flooding Reduction Algorithms Interopera January 2025 component). Therefore, it is not required that all information has to be flooded on the same CDS, for example, LSPs originated by different systems can use a different CDS each. To summarize the section above in simple terms, a pruner must choose at least one set of flooding links that guarantees that all information can reach all the nodes in the component. 2.1.4. Flooding Prunner Any flood reduction algorithm expecting to interoperate with other algorithms without understanding their semantics MUST follow the following rules, otherwise the algorithm is basically a ship in the night and cannot be expected to accommodate other algorithms in the network at the same time. 1. Each node of a pruner (except zero-pruner) MUST advertise in its flooded node information the currently active pruner. It MUST also understand such information as advertised by other nodes in the network. A node running a pruner MUST NOT assume implicitly that a node is a zero pruner or supports or runs the same algorithm. However, any pruner can safely assume that any node that does not advertise any running pruner in its node information MUST be a zero-pruner. Observe that a pruner does not need to understand how the algorithm of another pruner operates or its specific signalling type (or even whether it is centralized, centrally signalled or fully distributed). The only requirement is that every pruner agrees on the same signalling information which indicates the pruner currently running. 2. A pruner MUST NOT prune links in components other than the one it participates in or assume flooding behavior on links in other components (except in the case of a zero pruner where the flooding is well understood). In other words, each pruner is allowed to prune some links from flooding, but only strictly within its own component. Przygienda & Hegde Expires 17 July 2025 [Page 4] Internet-Draft Flooding Reduction Algorithms Interopera January 2025 3. A flooding pruner A MUST also include in its flooding CDS all links to adjacent components running non zero-pruner different from A. A node running pruner P that is different from zero- pruner SHOULD include in its flooding CDS all links to zero- pruners. It MAY use the known behavior of zero-pruner for further optimizations. Nevertheless, such optimizations MUST NOT assume that there is just a single Z| in the network. This is sufficient (but strictly speaking, more than necessary) to guarantee that the overall set of flooding CDSes within each component creates an overall flooding CDS over the whole network. In other words, the resulting set of links that still flood connects all nodes in the network. This document does not consider other approaches that guarantee a pruner property on e.g. a clique but assumes that such "ship in the night components" can be considered zero-pruners due to their implicit guarantee of correct flooding to nodes that are part of their component and floods on the edges to all other components. 2.2. Desirable Properties of the Flooding Prunner Framework Nodes within a component are free to use any kind of pruner to calculate optimized flooding. Any mode of computation, distributed or centralized will work fine as long as it adheres to Section 2.1.4. The framework allows but does not assume any centralized instance or election in a component. Computation and communication within each component is completely independent of other components. With the exception of a node having to advertise which prunner is active, no configuration is necessary unless the algorithm itself requires it. Przygienda & Hegde Expires 17 July 2025 [Page 5] Internet-Draft Flooding Reduction Algorithms Interopera January 2025 A node is free to choose a different pruner or zero-pruner at any point in time independent of all other nodes. It may end up in another component or become a zero-pruner with the maximum impact consisting of re-computation within two components that see such node leave or join. For a distributed algorithm, it is likely that only the adjoining nodes have to adjust their pruning decisions. That is to say, the framework allows for node-by-node deployment or migration of pruners without network-wide re-computation of optimized flooding. This is obviously critical to the stability of large networks that may not converge within reasonable time if the whole network were to revert back to zero-prunning due to network-wide impact. However, such behavior cannot be excluded for example in case of election problems due to misconfiguration or topological separation of nodes if the whole network runs a single pruner relying on centralized election. The network itself cannot ensure correctness of a pruner or prevent a pruner having a blast radius of the whole component depending upon the algorithm and signalling used. Though the framework provides extreme operational flexibility when deploying pruners, the most likely scenarios are a node-by-node deployment of a single pruner in addition to zero-pruner or, should the necessity arise, a node-by-node migration to another pruner. 2.3. Example Included in HTML/PDF only Figure 1: Network of Mixed Prunners Figure 1 illustrates a network with three pruners running. Two components run pruner A and are denoted as A|' and A|'' and one component runs pruner B. Remaining three components run a zero- pruner (annotated as Z|', Z|'' and Z|'''). CDSes within components are shown by indicating the links that were pruned from flooding as crossed out. Additionally, the links that are included to connect the CDS of the component following Section 2.1.4 have been made thicker. Despite multiple algorithms and components being present in the network, the complete graph is obviously still covered by the involved CDSes. Figure 1 also illustrates why the overall CDS can easily be more than just a spanning tree of the overall network. A node seeing its neighbor running another algorithm cannot always decide based on local knowledge whether the link should be included in flooding or not. Such a decision could be based on the overall view of the network using some global tie-breaking algorithm. However, due to the potential long flooding paths and one-link minimal cuts such an algorithm is not considered here but could be proposed in the future. Przygienda & Hegde Expires 17 July 2025 [Page 6] Internet-Draft Flooding Reduction Algorithms Interopera January 2025 2.4. Signalling The only signalling necessary is a Sub-TLV of the IS-IS Router Capability TLV-242 that is defined in [RFC7981] with the following format. The Sub-TLV MUST be advertised by a node that is actively running any pruner except zero-pruner and the absence of this Sub-TLV signifies a node being a 'zero-pruner'. 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 | Algorithm | Version | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2 * Type: TBD1 * Length: 2 * Algorithm: 8 bits of a numeric identifier in the range 0 .. 255 that identifies the algorithm used to calculate CDS (flooding topology) of the component. * Version: 8 bits of the algorithm version. Whether versions of the same algorithm can be considered as the same component by the involved algorithm or not is governed by each algorithm independently. All other algorithms MUST consider the versions of an algorithm as different algorithms for the purpose of Section 2.1.4. 3. Security Considerations This document outlines framework for modifications to an IGP protocol for operation on high density network topologies. Implementations SHOULD implement the according cryptographic authentication, as described in e.g. [RFC5304], and should enable other security measures in accordance with best common practices for the relevant IGP protocol. 4. Contributors The following people have contributed to this draft and are mentioned without any particular order: Jordan Head, Acee Lindem, Raj Chetan and Tony Li. 5. Normative References Przygienda & Hegde Expires 17 July 2025 [Page 7] Internet-Draft Flooding Reduction Algorithms Interopera January 2025 [RFC7981] Ginsberg, L., Previdi, S., and M. Chen, "IS-IS Extensions for Advertising Router Information", RFC 7981, DOI 10.17487/RFC7981, October 2016, . 6. Informative References [RFC5304] Li, T. and R. Atkinson, "IS-IS Cryptographic Authentication", RFC 5304, DOI 10.17487/RFC5304, October 2008, . [RFC5449] Baccelli, E., Jacquet, P., Nguyen, D., and T. Clausen, "OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks", RFC 5449, DOI 10.17487/RFC5449, February 2009, . [RFC5614] Ogier, R. and P. Spagnolo, "Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding", RFC 5614, DOI 10.17487/RFC5614, August 2009, . [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, June 2017, . Authors' Addresses Tony Przygienda Juniper Networks Email: prz@juniper.net Shraddha Hegde Juniper Networks Email: shraddha@juniper.net Przygienda & Hegde Expires 17 July 2025 [Page 8]