Network Working Group T. Przygienda
Internet-Draft S. Hegde
Intended status: Standards Track Juniper Networks
Expires: 26 August 2025 22 February 2025
Flooding Reduction Algorithms Framework
draft-prz-lsr-interop-flood-reduction-architecture-00
Abstract
This document introduces a framework 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 26 August 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 26 August 2025 [Page 1]
Internet-Draft Flooding Reduction Algorithms Framework February 2025
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Flooding Pruner Framework . . . . . . . . . . . . . . . . . . 2
2.1. Definitions and Axioms . . . . . . . . . . . . . . . . . 2
2.1.1. Maximum of One Flooding Pruner on a Node . . . . . . 3
2.1.2. Connected Component . . . . . . . . . . . . . . . . . 3
2.1.3. Flooding Connected Dominating Sets . . . . . . . . . 3
2.1.4. Rules for Flooding Pruners . . . . . . . . . . . . . 4
2.2. Beneficial Properties of the Flooding Pruner Framework . 5
2.3. Example . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4. Signaling . . . . . . . . . . . . . . . . . . . . . . . . 6
3. Security Considerations . . . . . . . . . . . . . . . . . . . 7
4. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 7
5. Normative References . . . . . . . . . . . . . . . . . . . . 7
6. Informative References . . . . . . . . . . . . . . . . . . . 7
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 7
1. Introduction
Scenarios exist where multiple distributed (or centralized) flood
reduction algorithms may be deployed simultaneously within an IGP
domain. These scenarios necessitate certain agreed on cooperative
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 to provide guidance toward the design of
algorithms with the necessary properties to ensure their
interoperable coexistence.
This document presents the necessary requirements for the involved
algorithms and the details of a framework for their interoperable
deployment. Although running multiple algorithms simultaneously may
not be a preferred operational choice, it is necessary if the
migration from one algorithm to another with minimal network
disruption is a priority. A migration itself may be caused by the
discovery of defects in the deployed algorithms or the deployment of
new algorithms that offer improvements.
2. Flooding Pruner Framework
2.1. Definitions and Axioms
This section outlines a framework that allows the operation of
multiple different flood reduction algorithms (called _flooding
pruners_ or _pruners_ from here on) in an interoperable fashion.
Przygienda & Hegde Expires 26 August 2025 [Page 2]
Internet-Draft Flooding Reduction Algorithms Framework February 2025
An important observation upfront, which will become clear later in
this section, is that full, non-optimized flooding presents a special
case of a pruner itself. Normal flooding includes all adjacencies
without any pruning, and hence we name it the _zero-pruner_ or
_zero"_ for short.
2.1.1. Maximum of One Flooding Pruner on a Node
This framework permits the use of at most one 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 connected
component.
2.1.2. Connected Component
A _connected component_ (or component for short) is defined as a
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 that are not connected, but that 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, we
denote those as P|' and P|''.
Zero-pruners also build 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 by components running zero-pruners (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 such
remaining links the term _flooding connected dominating set_ or CDS
for short (more precisely, a not necessarily loop-free edge
dominating set). 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|*. A|* is often not unique
for a component and many different sets of links can be a CDS. Nor
is it required that a CDS has to be loop-free since there may be many
different paths on the CDS between two nodes in a component.
Przygienda & Hegde Expires 26 August 2025 [Page 3]
Internet-Draft Flooding Reduction Algorithms Framework February 2025
Therefore, it is possible in a most extreme case that each LSP is
flooded on a different CDS.
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. Rules for Flooding Pruners
Any flood reduction algorithm expecting to interoperate with other
algorithms without understanding their semantics MUST adhere to the
following rules. Otherwise, the algorithm cannot be expected to
accommodate other algorithms in the network at the same time or is in
other words a ship in the night.
1. Each node of a pruner (except the 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 signaling type (or even whether it is
centralized, centrally signalled or fully distributed). The only
requirement is that every pruner agrees on the same signaling
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.
3. A flooding pruner A MUST also include in its flooding CDS all
links to adjacent components running a non _zero-pruner_
different from A. A node running pruner P that is different from
the _zero-pruner_ SHOULD include in its flooding CDS all links to
zero-pruners. It MAY use the known behavior the _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.
Przygienda & Hegde Expires 26 August 2025 [Page 4]
Internet-Draft Flooding Reduction Algorithms Framework February 2025
This document does not consider other approaches that guarantee a
pruner property on e.g. a clique. It 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 where connected to other components.
2.2. Beneficial Properties of the Flooding Pruner 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 pruner is
active, no configuration is necessary unless the algorithm itself
requires it.
A node is free to choose a different pruner or a _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 networkwide recomputation 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 to zero-pruning due to networkwide 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 signaling used.
Although 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 a zero-pruner or, if the
necessity arises, a node-by-node migration to another pruner.
2.3. Example
Included in HTML/PDF only
Przygienda & Hegde Expires 26 August 2025 [Page 5]
Internet-Draft Flooding Reduction Algorithms Framework February 2025
Figure 1: Network of Mixed Pruners
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 the _zero-
pruner_ algorithm (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 the rules listed in
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.
2.4. Signaling
The only signaling 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 a zero-pruner. The absence of this Sub-TLV
signifies a node being a 'zero-pruner' or an algorithm behaving
within its component in an equivalent fashion while also guaranteeing
flooding on links where it connects to other components.
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.
Przygienda & Hegde Expires 26 August 2025 [Page 6]
Internet-Draft Flooding Reduction Algorithms Framework February 2025
* 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 cryptographic authentication compliant to e.g.
[RFC5304], and should enable other security measures in accordance
with the 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
[RFC7981] Ginsberg, L., Previdi, S., and M. Chen, "IS-IS Extensions
for Advertising Router Information", RFC 7981,
DOI 10.17487/RFC7981, October 2016,
<https://www.rfc-editor.org/info/rfc7981>.
6. Informative References
[RFC5304] Li, T. and R. Atkinson, "IS-IS Cryptographic
Authentication", RFC 5304, DOI 10.17487/RFC5304, October
2008, <https://www.rfc-editor.org/info/rfc5304>.
Authors' Addresses
Tony Przygienda
Juniper Networks
Email: prz@juniper.net
Shraddha Hegde
Juniper Networks
Email: shraddha@juniper.net
Przygienda & Hegde Expires 26 August 2025 [Page 7]