Network Working Group                                      T. Przygienda
Internet-Draft                                                  S. Hegde
Intended status: Standards Track                        Juniper Networks
Expires: 17 July 2025                                    13 January 2025


        Flooding Reduction Algorithms Interoperability Framework
           draft-lsr-interop-flood-reduction-architecture-00

Abstract

   This document introduces a framework that makes it possible to deploy
   multiple flood reduction algorithms within the same IGP domain in an
   interoperable fashion.

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 17 July 2025.

Copyright Notice

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






Przygienda & Hegde        Expires 17 July 2025                  [Page 1]

Internet-Draft  Flooding Reduction Algorithms Interopera    January 2025


Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Flooding Prunner Framework  . . . . . . . . . . . . . . . . .   2
     2.1.  Definitions and Axioms  . . . . . . . . . . . . . . . . .   2
       2.1.1.  Maximum of One Flooding Prunner on a Node . . . . . .   3
       2.1.2.  Connected Component . . . . . . . . . . . . . . . . .   3
       2.1.3.  Flooding Connected Dominating Sets  . . . . . . . . .   3
       2.1.4.  Flooding Prunner  . . . . . . . . . . . . . . . . . .   4
     2.2.  Desirable Properties of the Flooding Prunner Framework  .   5
     2.3.  Example . . . . . . . . . . . . . . . . . . . . . . . . .   6
     2.4.  Signalling  . . . . . . . . . . . . . . . . . . . . . . .   7
   3.  Security Considerations . . . . . . . . . . . . . . . . . . .   7
   4.  Contributors  . . . . . . . . . . . . . . . . . . . . . . . .   7
   5.  Normative References  . . . . . . . . . . . . . . . . . . . .   7
   6.  Informative References  . . . . . . . . . . . . . . . . . . .   8
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   8

1.  Introduction

   Scenarios exist where multiple distributed (or centralized) flood
   reduction algorithms may be deployed simultaneously within an IGP
   domain.  These scenarios necessitate certain co-operative behaviors
   between the involved algorithms to ensure the correctness of the
   overall solution.  This is true in both permanent and transient
   (i.e., migration) deployment cases.  Fortunately, existing graph
   theory concepts allow us to provide guidance towards design of
   algorithms with the necessary properties to ensure their
   interoperable co-existence.

   This document presents the necessary requirements for the involved
   algorithms and the details of a framework for their interoperable
   deployment.  Though running multiple algorithms simultaneously may
   not be a preferred operational choice, it is necessary if the
   migration from one algorithm to another while ensuring minimal
   network disruption is a priority.  A migration itself may be caused
   by discovery of defects in deployed algorithms or deployment of new
   algorithms offering improvements.

2.  Flooding Prunner Framework

2.1.  Definitions and Axioms

   This section will outline a framework allowing the operation of
   multiple different flood reduction algorithms (called "flooding
   pruners" or "pruners" from here on) in an interoperable fashion.





Przygienda & Hegde        Expires 17 July 2025                  [Page 2]

Internet-Draft  Flooding Reduction Algorithms Interopera    January 2025


   As first important observation upfront, it will become clear later in
   this section that full, non-optimized flooding presents a special
   case of a pruner itself.  Normal flooding is including all
   adjacencies without any prunning and hence we name it the "zero-
   pruner" or "zero" for short.

2.1.1.  Maximum of One Flooding Prunner on a Node

   This framework permits maximum of a single active pruner on each
   node.  It allows to change a specific pruner at any time on any
   subset of nodes in the network while limiting the impact to the node
   itself and possibly the re-convergence of a set of nodes within its
   component.

2.1.2.  Connected Component

   A connected component (or component for short) is defined as subset
   of nodes running the same pruner (denoted as A) where each of the
   nodes can be connected to all other nodes by a path that traverses
   only nodes that run A.  Observe that there well may be in the network
   multiple components which are not connected, but run the same pruner.
   We denote a component for pruner P as P| and if two disjoint
   components running P are present in the network as P|' and P|''.

   Observe that zero-pruner also builds components denoted as Z| and its
   primes.

   Another way to visualize components is to consider a network running
   multiple pruners as "islands running non-zero algorithms" that are
   connected to each other via components running zero pruner (i.e.
   using normal flooding).

2.1.3.  Flooding Connected Dominating Sets

   A pruner may choose within its component a subset of links to flood
   while making sure that the component remains connected.  In other
   words, after suppressing flooding on some links within the component
   there must still exist paths consisting of the remaining links that
   connect each pair of nodes in the component.  We use for those
   remaining links the term flooding connected dominating set or CDS for
   short (more precisely, an edge dominating set which is not
   necessarily loop-free).  Such a CDS is colloquially often called
   "flooding topology" in context of flood reduction algorithms.  A
   simple spanning tree is an easily visualized special case of a CDS.
   We denote such a CDS for a component A| as A|*.  Observe that A|* is
   not unique for a component (i.e. many different sets of links can be
   a CDS).  Nor is it required that a CDS has to be loop-free (i.e.
   there may be many different paths on the CDS between two nodes in a



Przygienda & Hegde        Expires 17 July 2025                  [Page 3]

Internet-Draft  Flooding Reduction Algorithms Interopera    January 2025


   component).  Therefore, it is not required that all information has
   to be flooded on the same CDS, for example, LSPs originated by
   different systems can use a different CDS each.

   To summarize the section above in simple terms, a pruner must choose
   at least one set of flooding links that guarantees that all
   information can reach all the nodes in the component.

2.1.4.  Flooding Prunner

   Any flood reduction algorithm expecting to interoperate with other
   algorithms without understanding their semantics MUST follow the
   following rules, otherwise the algorithm is basically a ship in the
   night and cannot be expected to accommodate other algorithms in the
   network at the same time.

   1.  Each node of a pruner (except zero-pruner) MUST advertise in its
       flooded node information the currently active pruner.  It MUST
       also understand such information as advertised by other nodes in
       the network.  A node running a pruner MUST NOT assume implicitly
       that a node is a zero pruner or supports or runs the same
       algorithm.  However, any pruner can safely assume that any node
       that does not advertise any running pruner in its node
       information MUST be a zero-pruner.  Observe that a pruner does
       not need to understand how the algorithm of another pruner
       operates or its specific signalling type (or even whether it is
       centralized, centrally signalled or fully distributed).  The only
       requirement is that every pruner agrees on the same signalling
       information which indicates the pruner currently running.

   2.  A pruner MUST NOT prune links in components other than the one it
       participates in or assume flooding behavior on links in other
       components (except in the case of a zero pruner where the
       flooding is well understood).  In other words, each pruner is
       allowed to prune some links from flooding, but only strictly
       within its own component.















Przygienda & Hegde        Expires 17 July 2025                  [Page 4]

Internet-Draft  Flooding Reduction Algorithms Interopera    January 2025


   3.  A flooding pruner A MUST also include in its flooding CDS all
       links to adjacent components running non zero-pruner different
       from A.  A node running pruner P that is different from zero-
       pruner SHOULD include in its flooding CDS all links to zero-
       pruners.  It MAY use the known behavior of zero-pruner for
       further optimizations.  Nevertheless, such optimizations MUST NOT
       assume that there is just a single Z| in the network.  This is
       sufficient (but strictly speaking, more than necessary) to
       guarantee that the overall set of flooding CDSes within each
       component creates an overall flooding CDS over the whole network.
       In other words, the resulting set of links that still flood
       connects all nodes in the network.

   This document does not consider other approaches that guarantee a
   pruner property on e.g. a clique but assumes that such "ship in the
   night components" can be considered zero-pruners due to their
   implicit guarantee of correct flooding to nodes that are part of
   their component and floods on the edges to all other components.

2.2.  Desirable Properties of the Flooding Prunner Framework

   Nodes within a component are free to use any kind of pruner to
   calculate optimized flooding.  Any mode of computation, distributed
   or centralized will work fine as long as it adheres to Section 2.1.4.

   The framework allows but does not assume any centralized instance or
   election in a component.  Computation and communication within each
   component is completely independent of other components.

   With the exception of a node having to advertise which prunner is
   active, no configuration is necessary unless the algorithm itself
   requires it.



















Przygienda & Hegde        Expires 17 July 2025                  [Page 5]

Internet-Draft  Flooding Reduction Algorithms Interopera    January 2025


   A node is free to choose a different pruner or zero-pruner at any
   point in time independent of all other nodes.  It may end up in
   another component or become a zero-pruner with the maximum impact
   consisting of re-computation within two components that see such node
   leave or join.  For a distributed algorithm, it is likely that only
   the adjoining nodes have to adjust their pruning decisions.  That is
   to say, the framework allows for node-by-node deployment or migration
   of pruners without network-wide re-computation of optimized flooding.
   This is obviously critical to the stability of large networks that
   may not converge within reasonable time if the whole network were to
   revert back to zero-prunning due to network-wide impact.  However,
   such behavior cannot be excluded for example in case of election
   problems due to misconfiguration or topological separation of nodes
   if the whole network runs a single pruner relying on centralized
   election.  The network itself cannot ensure correctness of a pruner
   or prevent a pruner having a blast radius of the whole component
   depending upon the algorithm and signalling used.

   Though the framework provides extreme operational flexibility when
   deploying pruners, the most likely scenarios are a node-by-node
   deployment of a single pruner in addition to zero-pruner or, should
   the necessity arise, a node-by-node migration to another pruner.

2.3.  Example

                         Included in HTML/PDF only

                    Figure 1: Network of Mixed Prunners

   Figure 1 illustrates a network with three pruners running.  Two
   components run pruner A and are denoted as A|' and A|'' and one
   component runs pruner B.  Remaining three components run a zero-
   pruner (annotated as Z|', Z|'' and Z|''').  CDSes within components
   are shown by indicating the links that were pruned from flooding as
   crossed out.  Additionally, the links that are included to connect
   the CDS of the component following Section 2.1.4 have been made
   thicker.  Despite multiple algorithms and components being present in
   the network, the complete graph is obviously still covered by the
   involved CDSes.

   Figure 1 also illustrates why the overall CDS can easily be more than
   just a spanning tree of the overall network.  A node seeing its
   neighbor running another algorithm cannot always decide based on
   local knowledge whether the link should be included in flooding or
   not.  Such a decision could be based on the overall view of the
   network using some global tie-breaking algorithm.  However, due to
   the potential long flooding paths and one-link minimal cuts such an
   algorithm is not considered here but could be proposed in the future.



Przygienda & Hegde        Expires 17 July 2025                  [Page 6]

Internet-Draft  Flooding Reduction Algorithms Interopera    January 2025


2.4.  Signalling

   The only signalling necessary is a Sub-TLV of the IS-IS Router
   Capability TLV-242 that is defined in [RFC7981] with the following
   format.  The Sub-TLV MUST be advertised by a node that is actively
   running any pruner except zero-pruner and the absence of this Sub-TLV
   signifies a node being a 'zero-pruner'.

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |     Type      |     Length    | Algorithm     |  Version      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                                  Figure 2

   *  Type: TBD1

   *  Length: 2

   *  Algorithm: 8 bits of a numeric identifier in the range 0 .. 255
      that identifies the algorithm used to calculate CDS (flooding
      topology) of the component.

   *  Version: 8 bits of the algorithm version.  Whether versions of the
      same algorithm can be considered as the same component by the
      involved algorithm or not is governed by each algorithm
      independently.  All other algorithms MUST consider the versions of
      an algorithm as different algorithms for the purpose of
      Section 2.1.4.

3.  Security Considerations

   This document outlines framework for modifications to an IGP protocol
   for operation on high density network topologies.  Implementations
   SHOULD implement the according cryptographic authentication, as
   described in e.g.  [RFC5304], and should enable other security
   measures in accordance with best common practices for the relevant
   IGP protocol.

4.  Contributors

   The following people have contributed to this draft and are mentioned
   without any particular order: Jordan Head, Acee Lindem, Raj Chetan
   and Tony Li.

5.  Normative References




Przygienda & Hegde        Expires 17 July 2025                  [Page 7]

Internet-Draft  Flooding Reduction Algorithms Interopera    January 2025


   [RFC7981]  Ginsberg, L., Previdi, S., and M. Chen, "IS-IS Extensions
              for Advertising Router Information", RFC 7981,
              DOI 10.17487/RFC7981, October 2016,
              <https://www.rfc-editor.org/info/rfc7981>.

6.  Informative References

   [RFC5304]  Li, T. and R. Atkinson, "IS-IS Cryptographic
              Authentication", RFC 5304, DOI 10.17487/RFC5304, October
              2008, <https://www.rfc-editor.org/info/rfc5304>.

   [RFC5449]  Baccelli, E., Jacquet, P., Nguyen, D., and T. Clausen,
              "OSPF Multipoint Relay (MPR) Extension for Ad Hoc
              Networks", RFC 5449, DOI 10.17487/RFC5449, February 2009,
              <https://www.rfc-editor.org/info/rfc5449>.

   [RFC5614]  Ogier, R. and P. Spagnolo, "Mobile Ad Hoc Network (MANET)
              Extension of OSPF Using Connected Dominating Set (CDS)
              Flooding", RFC 5614, DOI 10.17487/RFC5614, August 2009,
              <https://www.rfc-editor.org/info/rfc5614>.

   [RFC8126]  Cotton, M., Leiba, B., and T. Narten, "Guidelines for
              Writing an IANA Considerations Section in RFCs", BCP 26,
              RFC 8126, DOI 10.17487/RFC8126, June 2017,
              <https://www.rfc-editor.org/info/rfc8126>.

Authors' Addresses

   Tony Przygienda
   Juniper Networks
   Email: prz@juniper.net


   Shraddha Hegde
   Juniper Networks
   Email: shraddha@juniper.net















Przygienda & Hegde        Expires 17 July 2025                  [Page 8]