Network Working Group T. Przygienda Internet-Draft S. Hegde Intended status: Standards Track Juniper Networks Expires: 21 April 2025 18 October 2024 Flooding Reduction Algorithm Interoperability Considerations draft-lsr-prz-interop-flood-reduction-architecture-00 Abstract In case multiple distributed (including a possible centralized one) flood reduction algorithms are deployed at the same time in an IGP domain the correctness of the overall solution preconditions certain co-operative behavior of involved algorithms. Under such conditions the correctness of the overall solution can be derived from resulting graph theoretical concepts easily. This document presents the necessary requirements on the deployed algorithms and the resulting framework. The situation of multiple algorithms in the network in steady state is per se not necessarily operationally desirable but must be, if minimal network disruption during such procedure is required, solved for possible migration scenarios caused by e.g. discovered defects or algorithm improvements. 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 21 April 2025. Copyright Notice Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. Przygienda & Hegde Expires 21 April 2025 [Page 1] Internet-Draft Flooding Reduction Algorithm Interoperab October 2024 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. Table of Contents 1. Flooding Prunner Framework . . . . . . . . . . . . . . . . . 2 1.1. Definitions and Axioms . . . . . . . . . . . . . . . . . 2 1.1.1. Maximum of One Flooding Prunner on a Node . . . . . . 2 1.1.2. Component . . . . . . . . . . . . . . . . . . . . . . 3 1.1.3. Flooding Connected Dominating Sets . . . . . . . . . 3 1.1.4. Flooding Prunner . . . . . . . . . . . . . . . . . . 3 1.2. Desirable Properties of the Flooding Prunner Framework . 4 1.3. Example . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Security Considerations . . . . . . . . . . . . . . . . . . . 6 3. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Normative References . . . . . . . . . . . . . . . . . . . . 6 5. Informative References . . . . . . . . . . . . . . . . . . . 6 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 7 1. Flooding Prunner Framework 1.1. Definitions and Axioms Following section will outline a framework of definitions and axioms to allow mixing different flood reduction algorithms, called `prunners` from here on, within an IGP domain in an interoperable manner. As first important observation upfront, it will become clear later in this section that full, non-optimized flooding presents a special case of a prunner itself being an operation including all adjacencies and hence we name it the "zero-prunner" or "zero" for short. 1.1.1. Maximum of One Flooding Prunner on a Node This framework allows maximum of a single active prunner on each node (which was implied by the previous paragraph silently) while it allows changing a specific prunner at any time on any subset of nodes in the network while limiting the impact to the node and the convergence of nodes in its component. Przygienda & Hegde Expires 21 April 2025 [Page 2] Internet-Draft Flooding Reduction Algorithm Interoperab October 2024 1.1.2. Component A component is defined as subset of nodes running a prunner algorithm denoted as A where each of the nodes is connected to all others by a path traversing adjacencies with A on both sides. Another way to think about this is that by removing all adjacencies with different prunners on both sides of the adjacency creates several non-connected components (partitions), each running a different prunner. Observe that there may be in the network very well multiple components which are not connected but run the same prunner. We denote a component for prunner A as A| and if two disjoint components running A are present in the network as A|' and A|''. Observe that zero-prunner also builds components denoted as Z| and its primes. 1.1.3. Flooding Connected Dominating Sets A flooding prunner may choose within its component a subset of links to flood on so that the component remains connected. In other words, there must be a path over such links connecting each node in the component of the prunner. We call this a flooding connected dominating set (more precisely, an edge dominating set which is not necessarily minimal of which e.g. a simple spanning tree is an easily visualized special case) or CDS for short, and denote it for a component A| as A|*. Observe that A|* is not unique to a component and hence can be different for different information flooded, e.g. LSPs originated by different systems. In simple words again, the algorithm must choose a set of links that guarantee at minimum that flooding reaches all the nodes in the component. 1.1.4. Flooding Prunner Any flood reduction algorithm expecting to interoperate with other algorithms 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 flooding prunner, except zero-prunner, MUST advertise in its flooded node information the prunner currently operating _or_ being capable to operate on the node and it MUST understand such information as advertised by other nodes in the network, i.e. not assume implicitly that a node is a zero prunner or supporting/running the same algorithm. With that, any prunner can safely assume that any node that does not advertise any additional flood reduction signalling MUST be a zero-prunner. Przygienda & Hegde Expires 21 April 2025 [Page 3] Internet-Draft Flooding Reduction Algorithm Interoperab October 2024 2. A flooding prunner is an algorithm A building a CDS denoted as A|* over its component that MUST additionally include in flooding CDS all links to adjacent components running non zero-prunner algorithm different from A. A node running algorithm A different from zero-prunner SHOULD include in its flooding CDS all links to zero-prunners but MAY use the known behavior of zero-prunner for further optimizations (though the optimization 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 CDS within each component creates an overall flooding CDS over the whole network or in other words, the resulting set of links that still flood connects all nodes in the network. This document does not consider further approaches that guarantee a prunner property on e.g. a clique but assumes that such "ship in the night components" can be considered zero prunners due to their implicit guarantee of correct flooding to nodes being part of their component and floods on the edges to all other components. 1.2. Desirable Properties of the Flooding Prunner Framework Nodes within a component are free to use any kind of prunner algorithm to calculate optimized flooding. Any mode of computation, distributed or centralized will work fine as long as Section 1.1.4 is respected. 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. Except advertising which prunner is active on a node no configuration is necessary if the prunner algorithm itself does not need further configuration, i.e. is completely independent on each node. Przygienda & Hegde Expires 21 April 2025 [Page 4] Internet-Draft Flooding Reduction Algorithm Interoperab October 2024 A node is free to choose a different prunner or zero-prunner at any point in time independent of all other nodes. It may end up in another component or become a zero-prunner and the maximum impact is re-computation within two components that see such node leave or join but more likely, only adjoining nodes have to adjust their prunning decisions. In simple words, the framework allows for a node by node deployment or even migration of prunners without network wide re- computation of optimized flooding. This is obviously critical to stability of large networks that may not even converge within reasonable time anymore if the whole network reverts back to zero- prunning due to network wide impact based on election, misconfiguration of a single node or deployment of a single node that affects the flooding optimization of the complete network. However, a prunner within a single component may have a much wider blast radius depending on algorithm and signallilng used. Though the network provides extreme flexibility in deployment of prunners operationally the most likely scenario is a node-by-node deployment of a single prunner algorithm in the network in addition to zero-prunner and in case of necessity the node-by-node migration to another new prunner. 1.3. Example Included in HTML/PDF only Figure 1: Network of Mixed Prunners Figure 1 visualizes a network with three prunners running, two components with prunner A, one with prunner B and three components running zero-prunner, annotated hence as Z|', Z|'' and Z|'''. CDS within components are not visualized since they do not contribute to further understanding but the links that are included to connect the CDS of the component following Section 1.1.4 are made fat. Obviously the overall graph is connected despite several algorithms and components the network encompasses on such, most likely not very likely, deployment. Przygienda & Hegde Expires 21 April 2025 [Page 5] Internet-Draft Flooding Reduction Algorithm Interoperab October 2024 Figure 1 also visualizes why the overall CDS can be easily more than a spanning tree of the overall network. A node seeing locally its neighbor running another algorithm cannot decide easily based simply on local knowledge whether the link should be included in flooding but could do so based on the overall view of the network of course and by some tie-breaking an algorithm to prune overall coverage to a spanning tree could be devised. Due to possible resulting long flooding paths and one link minimal cuts such an algorithm is not considered here. Of course in the future such an algorithm can be proposed with the nodes advertising whether they run such a 'prunner- of-prunners' while the absence of prunning can be denoted as 'zero- meta-prunner' to extend the symmetry of this solution recursively. 2. 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. 3. Contributors The following people have contributed to this draft and are mentioned without any particular order: Acee Lindem, Raj Chetan. 4. Normative References [RFC7981] Ginsberg, L., Previdi, S., and M. Chen, "IS-IS Extensions for Advertising Router Information", RFC 7981, DOI 10.17487/RFC7981, October 2016, . 5. 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, . Przygienda & Hegde Expires 21 April 2025 [Page 6] Internet-Draft Flooding Reduction Algorithm Interoperab October 2024 [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 21 April 2025 [Page 7]