An Algorithm for Computing Dynamic Flooding Topologies

Document Type Replaced Internet-Draft (individual)
Authors Sarah Chen  , Tony Li 
Last updated 2020-03-03
Replaced by draft-ietf-lsr-flooding-topo-min-degree
Stream (None)
Intended RFC status (None)
Expired & archived
pdf htmlized (tools) htmlized bibtex
Stream Stream state (No stream defined)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state Replaced by draft-ietf-lsr-flooding-topo-min-degree
Telechat date
Responsible AD (None)
Send notices to (None)

This Internet-Draft is no longer active. A copy of the expired Internet-Draft can be found at


Link-state routing protocols suffer from excessive flooding in dense network topologies. Dynamic flooding [I-D.ietf-lsr-dynamic-flooding] alleviates the problem by decoupling the flooding topology from the physical topology. Link-state protocol updates are flooded only on the sparse flooding topology while data traffic is still forwarded on the physical 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 as a flooding topology in 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 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.


Sarah Chen (
Tony Li (

(Note: The e-mail addresses provided for the authors of this Internet-Draft may no longer be valid.)