An Algorithm for Computing Dynamic Flooding Topologies
draft-ietf-lsr-dynamic-flooding-algorithm-04

Internet Engineering Task Force                                  S. Chen
Internet-Draft                                           Arista Networks
Intended status: Experimental                                      T. Li
Expires: 4 January 2027                       Hewlett Packard Enterprise
                                                             3 July 2026

         An Algorithm for Computing Dynamic Flooding Topologies
              draft-ietf-lsr-dynamic-flooding-algorithm-04

Abstract

   Link-state routing protocols suffer from excessive flooding in dense
   network topologies.  Dynamic flooding alleviates the problem by
   decoupling the flooding topology from the base topology.  Link-state
   protocol updates are flooded only on the sparse flooding topology
   while data traffic is still forwarded on the base topology.

   This document describes an algorithm to obtain a sparse subgraph from
   a dense graph.  The resulting subgraph has certain desirable
   properties and can be used by a centralized Area Leader to compute a
   flooding topology for dynamic flooding.

   This document discloses the algorithm that we have developed in order
   to make it easier for other developers to implement similar
   algorithms.  We do not claim that our algorithm is optimal, rather it
   is a pragmatic effort and we expect that further research and
   refinement can improve the results.

   We are not currently proposing that this algorithm be standardized,
   nor that the working group use this as a basis for further
   standardization work, however we have no objections if the working
   group chooses to do so.  This document is published as an
   Experimental RFC to gain operational and implementation experience
   with the specified dynamic flooding algorithm.  The intent is to
   assess the suitability of this algorithm for advancement to the
   Standards Track as a Proposed Standard, pending sufficient deployment
   experience and feedback from the community.

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/.

Chen & Li                Expires 4 January 2027                 [Page 1]
Internet-Draft         Dynamic Flooding Algorithm              July 2026

   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 4 January 2027.

Copyright Notice

   Copyright (c) 2026 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.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Experimental Status . . . . . . . . . . . . . . . . . . .   3
       1.1.1.  Experiment Duration . . . . . . . . . . . . . . . . .   4
       1.1.2.  Success Criteria  . . . . . . . . . . . . . . . . . .   4
   2.  Problem Statement . . . . . . . . . . . . . . . . . . . . . .   5
   3.  Algorithm Outline . . . . . . . . . . . . . . . . . . . . . .   5
   4.  Algorithm Details . . . . . . . . . . . . . . . . . . . . . .   7
     4.1.  Initial Cycle Setup . . . . . . . . . . . . . . . . . . .   7
     4.2.  Arc Path Selection  . . . . . . . . . . . . . . . . . . .   8
     4.3.  Exceptions  . . . . . . . . . . . . . . . . . . . . . . .   9
     4.4.  LANs  . . . . . . . . . . . . . . . . . . . . . . . . . .  10
   5.  Example . . . . . . . . . . . . . . . . . . . . . . . . . . .  10
   6.  Security Considerations . . . . . . . . . . . . . . . . . . .  11
   7.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  12
   8.  Normative References  . . . . . . . . . . . . . . . . . . . .  12
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  12

1.  Introduction

   In [RFC9667], dynamic flooding is proposed to reduce the flooding of
   link-state protocol packets in the network.  The basic idea is to
   find a sparse flooding topology from the base topology and flood
   link-state updates, i.e., IS-IS Link-State Protocol Data Units
   (LSPDUs or LSPs) and OSPF Link-State Advertisements (LSAs), only on
   the flooding topology.  The flooding topology should have the

Chen & Li                Expires 4 January 2027                 [Page 2]
Internet-Draft         Dynamic Flooding Algorithm              July 2026

   following properties:

   1.  It should include all nodes in the area.  This ensures that LSPs
       can reach all nodes.

   2.  It should be biconnected if possible.  This ensures that the LSP
       delivery is resilient to a single node or link failure.

   3.  It has a limited diameter.  Being a subgraph, the flooding
       topology often has a larger diameter than the topology.  A larger
       diameter indicates a longer convergence time.  The tradeoff
       between flooding reduction and convergence should be considered
       during the flooding topology computation.

   4.  It has a balanced degree of distribution.  The degree of a node
       on the flooding topology indicates its burden in flooding LSPs.
       It is desirable to balance this burden across multiple nodes.
       Hence, the degree of each node should also be considered during
       flooding topology computation.

   More discussion of these properties can be found in [RFC9667].

   With the above properties in mind, we propose an iterative algorithm
   to compute the flooding topology.  This is a centralized algorithm
   and does not require its own IGP algorithm code point.

1.1.  Experimental Status

   This specification is published with Experimental status to allow the
   Internet community to gain experience with this dynamic flooding
   algorithm prior to considering it for advancement to the Standards
   Track.  The experiment is intended to determine:

   1.  Whether the algorithm operates as described under real-world
       conditions and at scale,

   2.  Whether implementations interoperate correctly across diverse
       environments,

   3.  Whether the algorithm's performance and security properties hold
       in operational deployments, and

   4.  Whether there are unforeseen interactions with existing protocols
       or mechanisms.

Chen & Li                Expires 4 January 2027                 [Page 3]
Internet-Draft         Dynamic Flooding Algorithm              July 2026

   Implementors and operators who deploy this specification are
   encouraged to document their experiences and share feedback with the
   LSR Working Group at lsr@ietf.org.  Such feedback will be
   instrumental in evaluating whether this specification should be
   advanced to Proposed Standard status.

1.1.1.  Experiment Duration

   The LSR WG may review reported implementation and deployment
   experience periodically and decide whether to revise, retire, or
   advance the specification.  A report on the outcomes of the
   experiment will be produced prior to any decision to advance or
   retire this specification.

1.1.2.  Success Criteria

   Advancement of this specification to Proposed Standard will be
   considered if the following criteria are met:

   1.  At least 3 independent implementations are known to exist and to
       interoperate correctly.  As this is a centralized algorithm, an
       implementation must generate valid flooding topologies that are
       correctly interpreted by other systems in the area that implement
       [RFC9667].

   2.  Operational deployment experience has been documented and
       reported to the Working Group.

   3.  No fundamental technical objections to the algorithm's design
       have emerged from the experiment.

   4.  The Security Considerations identified in Section Section 6 have
       been validated or updated based on operational experience.

   5.  The operational quality of the computed topology produced by the
       algorithm is acceptable in deployments.

   6.  The flooding topology produced by the algorithm demonstrates
       acceptable convergence and flooding reduction.

   7.  The algorithm demonstrates robustness under topology changes.

Chen & Li                Expires 4 January 2027                 [Page 4]
Internet-Draft         Dynamic Flooding Algorithm              July 2026

2.  Problem Statement

   We model the base topology as an undirected connected graph.  Each
   system or pseudonode in the area is represented by a node in the
   graph.  An edge connects two nodes when the LSDB indicates two-way
   connectivity between them, consistent with the [RFC9667] connected-
   network-graph construction.  Given the set of the nodes and the set
   of edges, we propose an algorithm to compute a biconnected (if
   possible) subgraph that covers all nodes.  The subgraph is computed
   with consideration of diameter and node degree.

   The input to the algorithm is the contents of the Area Leader's LSDB.
   This may include:

   1.  overloaded nodes

   2.  nodes that do not support dynamic flooding

   3.  parallel links

   4.  links temporarily enabled for flooding

   5.  LAN/pseudonode edges and pseudonodes

3.  Algorithm Outline

   A simple cycle that covers all nodes is a biconnected subgraph with
   balanced node degrees.  While it has some desirable properties, a
   simple cycle is not suitable as a flooding topology at large scale.
   With N nodes in the area, a link-state update has to take N/2 hops to
   reach all nodes.  The undue propagation delay causes a long
   convergence time.

   The proposed algorithm constructs a subgraph composed of small
   overlapping cycles.  The base graph is denoted by G(V, E), where V is
   the set of all nodes in this area, and E is the set of edges.  The
   subgraph to be computed is denoted by G'({}, {}), which starts with
   an empty set of nodes and an empty set of edges.

   1.  Select a subset of nodes V(0) from V and a subset of edges E(0)
       from E to form an initial cycle.  This cycle is added to the
       subgraph: G'(V(0), E(0)).

Chen & Li                Expires 4 January 2027                 [Page 5]
Internet-Draft         Dynamic Flooding Algorithm              July 2026

   2.  Select a subset of nodes V(i) and a subset of edges E(i), that
       are not included in the current subgraph.  That is, V(i) is
       selected from V - V(0) - ... - V(i-1) and E(i) is selected from E
       - E(0) - ... - E(i-1).  These nodes and the edges are selected to
       form an arc path whose two endpoints are included in the current
       subgraph.  This arc path is added to the subgraph: G'( V(0) +
       V(1) + ... + V(i), E(0) + E(1) + ... + E(i) ).

   3.  Repeat step 2 until all nodes are included in the subgraph G'.

   The subgraph constructed by this algorithm has the following
   properties:

   1.  It covers all nodes in the area.

   2.  If the base graph contains a biconnected subgraph covering all
       nodes, and no LAN optimization or cut-edge exception is used that
       deliberately includes singly connected portions, the constructed
       subgraph is biconnected.  This can be easily proven by induction.
       Specifically, the initial cycle is biconnected.  Adding an arc
       path, whose two endpoints differ, to a biconnected subgraph
       maintains the biconnectivity of the subgraph.

   3.  For non-biconnected base graphs, the algorithm returns a
       connected flooding topology that is biconnected where possible,
       with unavoidable cut edges included for connectivity.

   4.  It has a limited diameter.  By selecting small cycles, the
       subgraph will have a smaller diameter.  More specifically, the
       implementation can pick endpoints of each arc path to reduce the
       diameter of the subgraph.  The degree of a node in the subgraph
       is determined by the number of arc paths it is on.  By carefully
       selecting the arc endpoints, we may balance the node degrees.

   Together with the encoding scheme in [RFC9667], this algorithm can be
   used to implement centralized dynamic flooding.  The area leader can
   build the base graph from its link-state database (LSDB), apply this
   algorithm to compute the flooding topology, and then encode it into
   the IS-IS Flooding Path TLV or OSPF Flooding Path TLV defined by
   [RFC9667], depending on the protocol.  In a topology change event,
   the area leader can repeat the above process and send out the new
   flooding topology.

Chen & Li                Expires 4 January 2027                 [Page 6]
Internet-Draft         Dynamic Flooding Algorithm              July 2026

4.  Algorithm Details

   The outlined algorithm allows for different approaches to find the
   initial cycle and subsequent arc paths.  We do not intend to find the
   theoretically optimal solution.  Our aim is to find a practical
   approach that works for any connected base graph, and is also easy to
   implement.

   Since this algorithm is intended for centralized computation, choices
   such as DFS depth limit, tie-breaking, neighbor ordering, and
   endpoint selection are implementation specific and do not affect
   protocol interoperability, provided the resulting topology is
   correctly encoded using [RFC9667].

4.1.  Initial Cycle Setup

   The initial cycle forms a base of the subgraph computation.
   Intuitively, we would like to place the initial cycle around the
   centroid of the base graph, and gradually expand it outwards.
   Complicated graph analysis can help, but is not desired.

   We propose to select a starting node and then search a path that ends
   at this node.  We suggest selecting the node with the highest degree
   as the starting node.  The degree of each node can be easily
   determined when the base graph is constructed from the LSDB.
   Starting from this node, we perform a depth-first search (DFS) for a
   limited number of steps, and then a breadth-first search (BFS) to
   find the shortest path back to the starting node.  The restriction of
   the DFS depths and the use of BFS effectively help limit the diameter
   of the initial cycle.  Below is a summary of the procedure.  We omit
   the details of the well-known DFS and BFS algorithms.

   1.  Let V(0) = [] be the list of nodes on the initial cycle.

   2.  Find the starting node, denoted by n0.  V(0) = [n0].

   3.  Perform DFS starting from n0 until either the first leaf is
       reached or the depth reaches a preset limit.  The visited nodes
       are denoted by n1, n2, ..., ni, where i < DFS depth limit, and
       added to the list V(0) in order.

   4.  Mark nodes in V(0) as visited to avoid BFS visiting these nodes.
       Then perform BFS to find the shortest path from ni to n0.  Append
       nodes on the shortest path to V(0).  Since this is a cycle, node
       n0 appears twice in V(0): the first and the last places.

Chen & Li                Expires 4 January 2027                 [Page 7]
Internet-Draft         Dynamic Flooding Algorithm              July 2026

   If the selected DFS path and the subsequent BFS search find a return
   path to the starting node, the resulting path forms a cycle.  If no
   such path is found, the exception handling in Section 4.3 is used.

4.2.  Arc Path Selection

   After obtaining an initial cycle, we recursively add arc paths to the
   subgraph until all nodes are included.  Each arc path's two endpoints
   are chosen from the current subgraph.  This ensures that the
   resulting subgraph remains biconnected.  To limit the diameter of the
   resulting subgraph, we select an arc path with limited length and
   attach it closer to the initial cycle.

   In each iteration, we have a starting subgraph, which includes the
   initial cycle and the arc paths obtained in earlier iterations.  We
   first select a node from the starting subgraph, that has at least one
   neighbor that is not in the starting subgraph.  To balance the degree
   distribution, we prefer to select a node that has the least degree in
   the starting subgraph.  Meanwhile, we intend to place the new arc
   path closer to the initial cycle, which will help reduce the diameter
   of the resulting subgraph.  As the number of iterations increases, it
   becomes hard to find such nodes that meet both conditions.  A
   tradeoff between the node degree and the node distance to the initial
   cycle has to be made.  This tradeoff is implementation specific.

   Starting from the selected node, we perform a DFS for a limited
   number of steps in the base graph to include nodes and edges that do
   not belong to the starting subgraph.  Then BFS is performed to find
   the shortest path back to any node in the starting subgraph except
   the starting node of this iteration.  The resulting path is combined
   with the starting subgraph to generate a new subgraph, which serves
   as the starting subgraph in the next iteration.  The iteration is
   repeated until all nodes in the base graph are included in the
   subgraph.

   The procedure in each iteration is very similar to the one used to
   find the initial cycle, except that the two endpoints of the new path
   do not match:

   1.  Let V(i) = [] be the list of nodes found in the i-th iteration.
       The starting subgraph includes nodes in V(0) + ... + V(i-1), and
       edges between each pair of adjacent nodes in each node list V(j).

   2.  Select a starting node n0 for this iteration from the starting
       subgraph.  V(i) = [n0].

Chen & Li                Expires 4 January 2027                 [Page 8]
Internet-Draft         Dynamic Flooding Algorithm              July 2026

   3.  Mark all nodes in V(0) + ... + V(i-1) as visited.  Then perform
       DFS from n0 until either the first leaf is reached or the depth
       exceeds a preset limit.  Nodes visited in this iteration are
       denoted by n1, n2, ..., ni in order, and appended to the list
       V(i).

   4.  Mark all nodes in V(0) + ... + V(i-1) + V(i) as visited.  Then
       perform BFS to find the shortest path from ni to any node in V(0)
       + ... + V(i-1) - [n0], where n0 is the starting node in this
       iteration.  If a path is found, append its nodes to V(i) and
       repeat the iteration from step 1.

   By correctly marking the visited nodes before DFS and BFS, we ensure
   that the obtained arc path (if it exists) has two endpoints and only
   these two points on the starting subgraph.

4.3.  Exceptions

   If the base graph is biconnected, there exists a simple cycle between
   any two nodes.  We are thus ensured to find one arc path in each
   iteration and the algorithm described above will yield a biconnected
   subgraph that covers all nodes in the base graph.  Otherwise,
   however, we may not be able to find an arc path with both endpoints
   belonging to the starting subgraph in that iteration.  When this
   happens, we know that the edge between the last node found by DFS and
   its parent is a cut edge in the base graph.  For connectivity, this
   edge must be included in the resulting subgraph.  Hence, when step 4
   (the BFS stage in earlier procedures) fails, we should amend it with
   the following:

   5.  If the cut-edge case is detected, include the cut edge in the
       resulting topology and then start a new cycle search in the
       component reachable across that cut edge.

   6.  If BFS does not find a shortest path from ni, and V(i) contains
       more than two nodes, then remove the last node from V(i), and go
       back to step 4.

   Similarly, we might face the same problem when selecting the initial
   cycle.  We can apply step 6 until we find a cycle.  However, if we
   happen to find a cut edge, we can change the first neighbor of the
   starting node that is visited by the DFS and repeat the procedure.
   If all edges connecting to the starting node are cut edges, we can
   change the starting node.  If an initial cycle is not found after all
   the above efforts, indicating that the base graph does not have a
   cycle, then we will return the base graph as the result.

Chen & Li                Expires 4 January 2027                 [Page 9]
Internet-Draft         Dynamic Flooding Algorithm              July 2026

4.4.  LANs

   We model a pseudonode as a node in the base graph.  The proposed
   algorithm can be applied as-is.  There are, however, possible
   optimizations for the pseudonode case.  First, a pseudonode is not
   required to be on the flooding topology in this centralized
   algorithm, as pseudonodes do not actually participate in flooding.
   The algorithm can thus be terminated as soon as all real nodes are
   included in the subgraph.  Second, if a pseudonode is included on the
   flooding topology, all nodes connecting to this LAN will have to
   flood their LSPs to this LAN (see [RFC9667] Section 6.6).  Hence, if
   a pseudonode is included in the subgraph, it will automatically
   provide uni-connectivity to all of its neighbors that are not yet
   included.  Other edges may still be required to provide
   biconnectivity.  The algorithm can take advantage of this LAN
   property to reduce the edges in the subgraph.

5.  Example

   The proposed algorithm can be applied to any connected base graph.
   For ease of explanation, we consider a complete graph of 10 nodes and
   45 edges.  To limit the diameter of the resulting subgraph, we pre-
   set the maximum steps in the DFS to 3.

   1.  Let ni, i = 0, 1, ... 9, denote nodes in the base graph.

   2.  Find an initial cycle.

       a.  Without loss of generality, we select node n0 as the starting
           point.

       b.  Perform DFS from n0 for 3 steps.  We obtain a path n0 - n1 -
           n2 - n3.

       c.  Perform BFS from n3 to n0.  Since this is a complete graph,
           where every node is directly connected to any other node, the
           shortest path is only one hop away.

       d.  The initial cycle is found n0 - n1 - n2 - n3 - n0.

   3.  Find the first arc path.

       a.  Select a node on the initial cycle, say n0.

       b.  Perform DFS from n0 for 3 steps.  We obtain a path n0 - n4 -
           n5 - n6.

Chen & Li                Expires 4 January 2027                [Page 10]
Internet-Draft         Dynamic Flooding Algorithm              July 2026

       c.  Perform BFS from n6 to any node on the initial cycle except
           n0, i.e., {n1, n2, n3}. These three nodes have the same
           degree.  We may select any one of them as the endpoint.
           Suppose that n1 is selected.

       d.  The first arc path is found n0 - n4 - n5 - n6 - n1.

   4.  Find the second arc path.

       a.  When selecting the starting node for this path, we may
           consider the current node degree as well as the node distance
           to n0 (the starting point of the initial cycle).  We notice
           that both n0 and n1 have a degree of 3 while other nodes have
           a degree of 2.  Nodes n1, n3, n4 are the closest to n0.  We
           select a node with a lower degree and closer to n0.  Suppose
           n3 is selected.

       b.  Perform DFS from n3 for 3 steps.  We obtain a path n3 - n7
           -n8 - n9.

       c.  Perform BFS from n9 to any node except n3.  Using the same
           criteria in a. to select the endpoint, we select n4.

       d.  The second arc path is found n3 - n7 -n8 - n9 - n4.

   5.  The subgraph has included all nodes.  The iteration ends.

   The subgraph found by the proposed algorithm can be represented by
   three paths:

      n0 - n1 - n2 - n3 - n0

      n0 - n4 - n5 - n6 - n1

      n3 - n7 -n8 - n9 - n4

   The subgraph has 12 edges, significantly reduced from 45 in the base
   graph.  The highest node degree is 3 and the lowest node degree is 2.
   The diameter of the subgraph is 4, increased, as expected, from that
   of the base graph.

6.  Security Considerations

   This document introduces no new security issues.  Security issues
   within dynamic flooding are already discussed in [RFC9667].

Chen & Li                Expires 4 January 2027                [Page 11]
Internet-Draft         Dynamic Flooding Algorithm              July 2026

7.  IANA Considerations

   This document makes no requests of IANA.

   This document does not define a distributed-mode IGP algorithm for
   computing the flooding topology and therefore does not request an
   allocation from the IGP Algorithm Type For Computing Flooding
   Topology registry.

8.  Normative References

   [RFC9667]  Li, T., Ed., Psenak, P., Ed., Chen, H., Jalil, L., and S.
              Dontula, "Dynamic Flooding on Dense Graphs", RFC 9667,
              DOI 10.17487/RFC9667, October 2024,
              <https://www.rfc-editor.org/info/rfc9667>.

Authors' Addresses

   Sarah Chen
   Arista Networks
   5453 Great America Parkway
   Santa Clara, California 95054
   United States of America
   Email: sarahchen@arista.com

   Tony Li
   Hewlett Packard Enterprise
   Email: tony.li@tony.li

Chen & Li                Expires 4 January 2027                [Page 12]