Skip to main content

An Algorithm for Computing Dynamic Flooding Topologies

Document Type Expired Internet-Draft (individual)
Expired & archived
Authors Sarah Chen , Tony Li
Last updated 2020-03-03
RFC stream (None)
Intended RFC status (None)
Stream Stream state (No stream defined)
Consensus boilerplate Unknown
RFC Editor Note (None)
IESG IESG state Expired
Telechat date (None)
Responsible AD (None)
Send notices to (None)

This Internet-Draft is no longer active. A copy of the expired Internet-Draft is available in these formats:


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