An Algorithm for Computing Dynamic Flooding Topologies
draft-chen-lsr-dynamic-flooding-algorithm-00

Document Type Active Internet-Draft (individual)
Last updated 2020-03-03
Stream (None)
Intended RFC status (None)
Formats plain text html xml pdf htmlized bibtex
Stream Stream state (No stream defined)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date
Responsible AD (None)
Send notices to (None)
Internet Engineering Task Force                                  S. Chen
Internet-Draft                                                     T. Li
Intended status: Informational                           Arista Networks
Expires: 4 September 2020                                   3 March 2020

         An Algorithm for Computing Dynamic Flooding Topologies
              draft-chen-lsr-dynamic-flooding-algorithm-00

Abstract

   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.

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

Chen & Li               Expires 4 September 2020                [Page 1]
Internet-Draft         Dynamic Flooding Algorithm             March 2020

   This Internet-Draft will expire on 4 September 2020.

Copyright Notice

   Copyright (c) 2020 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 Simplified BSD License text
   as described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Problem Statement . . . . . . . . . . . . . . . . . . . . . .   3
   3.  Algorithm Outline . . . . . . . . . . . . . . . . . . . . . .   3
   4.  Algorithm Details . . . . . . . . . . . . . . . . . . . . . .   4
     4.1.  Initial Cycle Setup . . . . . . . . . . . . . . . . . . .   4
     4.2.  Arc Path Selection  . . . . . . . . . . . . . . . . . . .   5
     4.3.  Exceptions  . . . . . . . . . . . . . . . . . . . . . . .   6
     4.4.  LANs  . . . . . . . . . . . . . . . . . . . . . . . . . .   7
   5.  Example . . . . . . . . . . . . . . . . . . . . . . . . . . .   7
   6.  Security Considerations . . . . . . . . . . . . . . . . . . .   9
   7.  Informative References  . . . . . . . . . . . . . . . . . . .   9
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   9

1.  Introduction

   In [I-D.ietf-lsr-dynamic-flooding], 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
   physical topology and flood link-state protocol data units (LSPDUs or
   LSPs) only on the flooding topology.  The flooding topology should
   have the 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 physical topology.

Chen & Li               Expires 4 September 2020                [Page 2]
Internet-Draft         Dynamic Flooding Algorithm             March 2020

       A larger diameter indicates a longer convergence time.  The
Show full document text