| Internet-Draft | Flooding Reduction Algorithm Interoperab | October 2024 |
| Przygienda & Hegde | Expires 21 April 2025 | [Page] |
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.¶
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 (c) 2024 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.¶
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.¶
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.¶
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.¶
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.¶
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.¶
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.¶
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.¶
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.¶
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.¶
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.¶
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.¶
The following people have contributed to this draft and are mentioned without any particular order: Acee Lindem, Raj Chetan.¶