Internet-Draft Dynamic Flooding Algorithm August 2026
Chen & Li Expires 24 February 2027 [Page]
Workgroup:
Internet Engineering Task Force
Internet-Draft:
draft-ietf-lsr-dynamic-flooding-algorithm-05
Published:
Intended Status:
Experimental
Expires:
Authors:
S. Chen
Arista Networks
T. Li
Hewlett Packard Enterprise

An Algorithm for Computing Dynamic Flooding Topologies

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 the authors have developed in order to make it easier for other developers to implement similar algorithms. The authors do not claim that our algorithm is optimal, rather, it is a pragmatic effort and the authors expect that further research and refinement can improve the results.

The authors are not currently proposing that this algorithm be standardized, nor that the working group use this as a basis for further standardization work; however, the authors 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/.

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 24 February 2027.

▲

Table of Contents

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 following properties:

  1. It should include all reachable nodes in the area.
  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 base 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, this document describes 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.

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

2. Problem Statement

This algorithm models 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, this document describes 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

This section presents an overview of the algorithm. More details can be found in Section 4.

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 as an empty set of nodes and an empty set of edges, G'({}, {}).

  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 G' subgraph, so it becomes G'(V(0), E(0)).
  2. Select an arc path (V(i), E(i)) such that the first and last node are in G', the remaining nodes are not in G', and all edges are not in G'. That is, V(i) midpoints are selected from V - V(0) - ... - V(i-1) and E(i) is selected from E - E(0) - ... - E(i-1). This arc path is added to G', resulting in 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 reachable 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, an implementation 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 Area Node IDs TLV and the IS-IS Flooding Path TLV, the OSPF Area Router IDs TLV or the 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.

4. Algorithm Details

The outlined algorithm allows for different approaches to find the initial cycle and subsequent arc paths. The algorithm does not provide the theoretically optimal solution. Rather, the 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 depth-first search (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, the initial cycle should be around the centroid of the base graph, and the algorithm gradually expands outward. Complicated graph analysis can help, but is not desired.

The algorithm starts by selecting a starting node and then finding a path that ends at this node. The node with the highest degree seems to be a logical choice for 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, the algorithm performs a 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. The details of the well-known DFS and BFS algorithms are omitted for brevity.

  1. Let V(0) = [] be the list of nodes on the initial cycle.
  2. Choose a 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.

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, the algorithm recursively adds 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, the algorithm selects an arc path with limited length and attaches it closer to the initial cycle.

In each iteration, there is a starting subgraph, which includes the initial cycle and the arc paths obtained in earlier iterations. The algorithm first selects a node from the starting subgraph that has at least one neighbor that is not in the starting subgraph. To balance the degree distribution, the algorithm selects a node that has the least degree in the starting subgraph. Meanwhile, the algorithm tries 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, the algorithm performs 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].
  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, the algorithm ensures that the obtained arc path (if it exists) has two endpoints and only these two points in the starting subgraph.

4.3. Exceptions

If the base graph is biconnected, there exists a simple cycle between any two nodes. This ensures that the algorithm finds one arc path in each iteration and yields a biconnected subgraph that covers all nodes in the base graph. Otherwise, the algorithm may not be able to find an arc path with both endpoints belonging to the starting subgraph in that iteration. When this happens, 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, the above algorithm is amended with the following:

  1. 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.
  2. 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, the same problem may occur when selecting the initial cycle. Step 6 can be repeated until a cycle is found. However, if a cut edge is found, select a different first neighbor of the starting node to be visited by the DFS and repeat the procedure. If all edges connecting to the starting node are cut edges, select a different 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 return the base graph as the result.

4.4. LANs

A pseudonode is modeled 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, consider a complete graph of 10 nodes and 45 edges. To limit the diameter of the resulting subgraph, the maximum steps in the DFS is set to 3.

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

  2. Find an initial cycle.

    1. Without loss of generality, select node n0 as the starting point.
    2. Perform DFS from n0 for 3 steps. This produces a path n0 - n1 - n2 - n3.
    3. 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.
    4. The initial cycle is found: n0 - n1 - n2 - n3 - n0.
    5. G' is now the cycle n0 - n1 - n2 - n3 - n0.

  3. Find the first arc path.

    1. Select a node on the initial cycle, say n0.
    2. Perform DFS from n0 for 3 steps. This produces a path n0 - n4 - n5 - n6.
    3. 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. Select any one of them as the endpoint. Suppose that n1 is selected.
    4. The first arc path is found: n0 - n4 - n5 - n6 - n1.
    5. G' is now the paths n0 - n1 - n2 - n3 - n0, and n0 - n4 - n5 - n6 - n1.

  4. Find the second arc path.

    1. When selecting the starting node for this path, consider the current node degree as well as the node distance to n0 (the starting point of the initial cycle). 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. Select a node with a lower degree and closer to n0. Suppose n3 is selected.
    2. Perform DFS from n3 for 3 steps. This produces a path n3 - n7 - n8 - n9.
    3. Perform BFS from n9 to any node except n3. Using the same criteria in a. to select the endpoint, select n4.
    4. 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:

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. Operational Considerations

The operational considerations for this algorithm are the same as for any centralized algorithm as described in [RFC9667], and are all derived from that document.

The Area Leader election mechanism must be operating correctly and elect a single leader that all area nodes must converge on eventually. If there is no agreement on the Area Leader, there will be inconsistency throughout the area. As the Area Leader election algorithm is taken directly from the well-proven Designated Intermediate System election algorithm, no operational issues are anticipated in this function. An implementation SHOULD provide an indication of its Area Leader.

The Area Leader then must advertise the Area Leader sub-TLV and specify that it is using a centralized algorithm. This seems like this is very low operational risk as this is a constant value.

Only the Area Leader executes the algorithm found in this document. The Area Leader then advertises its results in the Flooding Path TLV and Area Node IDs TLV. If there are operational issues with any centralized algorithm, they can be detected by comparing these results to the actual physical topology.

Each node in the area is responsible for parsing these results and understanding its role in the flooding topology. An implementation SHOULD provide an indication of which adjacencies are on the flooding topology via some management plane mechanism. The details of this mechanism and implementation dependent and out of scope for this document.

Partial deployment of Dynamic Flooding is fully supported. If a node does not support Dynamic Flooding, then it is a legacy node and supports standard flooding, which implies that it floods on all interfaces. Thus, it is satisfying the expectations of the algorithm and flooding on the flooding topology. Of course, it will also flood on adjacencies that are not part of the flooding topology, and it will not help to reduce the flooding in the area.

The largest operational risk for Dynamic Flooding comes from topological changes, as detailed in [RFC9667], Section 6.8. If an implementation does not handle the partition of the flooding topology and temporary flooding correctly, it will result in partial flooding and inconsistent routing.

7. Security Considerations

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

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

9. 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, , <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
Tony Li
Hewlett Packard Enterprise