Flooding Reduction Algorithm Interoperability Considerations
draft-lsr-prz-interop-flood-reduction-architecture-00

Network Working Group                                      T. Przygienda
Internet-Draft                                                  S. Hegde
Intended status: Standards Track                        Juniper Networks
Expires: 21 April 2025                                   18 October 2024

      Flooding Reduction Algorithm Interoperability Considerations
         draft-lsr-prz-interop-flood-reduction-architecture-00

Abstract

   In case multiple distributed (including a possible centralized one)
   flood reduction algorithms are deployed at the same time in an IGP
   domain the correctness of the overall solution preconditions certain
   co-operative behavior of involved algorithms.  Under such conditions
   the correctness of the overall solution can be derived from resulting
   graph theoretical concepts easily.  This document presents the
   necessary requirements on the deployed algorithms and the resulting
   framework.  The situation of multiple algorithms in the network in
   steady state is per se not necessarily operationally desirable but
   must be, if minimal network disruption during such procedure is
   required, solved for possible migration scenarios caused by e.g.
   discovered defects or algorithm improvements.

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 21 April 2025.

Copyright Notice

   Copyright (c) 2024 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

Przygienda & Hegde        Expires 21 April 2025                 [Page 1]
Internet-Draft  Flooding Reduction Algorithm Interoperab    October 2024

   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.

Table of Contents

   1.  Flooding Prunner Framework  . . . . . . . . . . . . . . . . .   2
     1.1.  Definitions and Axioms  . . . . . . . . . . . . . . . . .   2
       1.1.1.  Maximum of One Flooding Prunner on a Node . . . . . .   2
       1.1.2.  Component . . . . . . . . . . . . . . . . . . . . . .   3
       1.1.3.  Flooding Connected Dominating Sets  . . . . . . . . .   3
       1.1.4.  Flooding Prunner  . . . . . . . . . . . . . . . . . .   3
     1.2.  Desirable Properties of the Flooding Prunner Framework  .   4
     1.3.  Example . . . . . . . . . . . . . . . . . . . . . . . . .   5
   2.  Security Considerations . . . . . . . . . . . . . . . . . . .   6
   3.  Contributors  . . . . . . . . . . . . . . . . . . . . . . . .   6
   4.  Normative References  . . . . . . . . . . . . . . . . . . . .   6
   5.  Informative References  . . . . . . . . . . . . . . . . . . .   6
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   7

1.  Flooding Prunner Framework

1.1.  Definitions and Axioms

   Following section will outline a framework of definitions and axioms
   to allow mixing different flood reduction algorithms, called
   `prunners` from here on, within an IGP domain in an interoperable
   manner.

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

1.1.1.  Maximum of One Flooding Prunner on a Node

   This framework allows maximum of a single active prunner on each node
   (which was implied by the previous paragraph silently) while it
   allows changing a specific prunner at any time on any subset of nodes
   in the network while limiting the impact to the node and the
   convergence of nodes in its component.

Przygienda & Hegde        Expires 21 April 2025                 [Page 2]
Internet-Draft  Flooding Reduction Algorithm Interoperab    October 2024

1.1.2.  Component

   A component is defined as subset of nodes running a prunner algorithm
   denoted as A where each of the nodes is connected to all others by a
   path traversing adjacencies with A on both sides.  Another way to
   think about this is that by removing all adjacencies with different
   prunners on both sides of the adjacency creates several non-connected
   components (partitions), each running a different prunner.  Observe
   that there may be in the network very well multiple components which
   are not connected but run the same prunner.  We denote a component
   for prunner A as A| and if two disjoint components running A are
   present in the network as A|' and A|''.

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

1.1.3.  Flooding Connected Dominating Sets

   A flooding prunner may choose within its component a subset of links
   to flood on so that the component remains connected.  In other words,
   there must be a path over such links connecting each node in the
   component of the prunner.  We call this a flooding connected
   dominating set (more precisely, an edge dominating set which is not
   necessarily minimal of which e.g. a simple spanning tree is an easily
   visualized special case) or CDS for short, and denote it for a
   component A| as A|*.  Observe that A|* is not unique to a component
   and hence can be different for different information flooded, e.g.
   LSPs originated by different systems.  In simple words again, the
   algorithm must choose a set of links that guarantee at minimum that
   flooding reaches all the nodes in the component.

1.1.4.  Flooding Prunner

   Any flood reduction algorithm expecting to interoperate with other
   algorithms 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 flooding prunner, except zero-prunner, MUST
       advertise in its flooded node information the prunner currently
       operating _or_ being capable to operate on the node and it MUST
       understand such information as advertised by other nodes in the
       network, i.e. not assume implicitly that a node is a zero prunner
       or supporting/running the same algorithm.  With that, any prunner
       can safely assume that any node that does not advertise any
       additional flood reduction signalling MUST be a zero-prunner.

Przygienda & Hegde        Expires 21 April 2025                 [Page 3]
Internet-Draft  Flooding Reduction Algorithm Interoperab    October 2024

   2.  A flooding prunner is an algorithm A building a CDS denoted as
       A|* over its component that MUST additionally include in flooding
       CDS all links to adjacent components running non zero-prunner
       algorithm different from A.  A node running algorithm A different
       from zero-prunner SHOULD include in its flooding CDS all links to
       zero-prunners but MAY use the known behavior of zero-prunner for
       further optimizations (though the optimization 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 CDS within each
       component creates an overall flooding CDS over the whole network
       or in other words, the resulting set of links that still flood
       connects all nodes in the network.

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

1.2.  Desirable Properties of the Flooding Prunner Framework

   Nodes within a component are free to use any kind of prunner
   algorithm to calculate optimized flooding.  Any mode of computation,
   distributed or centralized will work fine as long as Section 1.1.4 is
   respected.

   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.

   Except advertising which prunner is active on a node no configuration
   is necessary if the prunner algorithm itself does not need further
   configuration, i.e. is completely independent on each node.

Przygienda & Hegde        Expires 21 April 2025                 [Page 4]
Internet-Draft  Flooding Reduction Algorithm Interoperab    October 2024

   A node is free to choose a different prunner or zero-prunner at any
   point in time independent of all other nodes.  It may end up in
   another component or become a zero-prunner and the maximum impact is
   re-computation within two components that see such node leave or join
   but more likely, only adjoining nodes have to adjust their prunning
   decisions.  In simple words, the framework allows for a node by node
   deployment or even migration of prunners without network wide re-
   computation of optimized flooding.  This is obviously critical to
   stability of large networks that may not even converge within
   reasonable time anymore if the whole network reverts back to zero-
   prunning due to network wide impact based on election,
   misconfiguration of a single node or deployment of a single node that
   affects the flooding optimization of the complete network.  However,
   a prunner within a single component may have a much wider blast
   radius depending on algorithm and signallilng used.

   Though the network provides extreme flexibility in deployment of
   prunners operationally the most likely scenario is a node-by-node
   deployment of a single prunner algorithm in the network in addition
   to zero-prunner and in case of necessity the node-by-node migration
   to another new prunner.

1.3.  Example

                         Included in HTML/PDF only

                    Figure 1: Network of Mixed Prunners

   Figure 1 visualizes a network with three prunners running, two
   components with prunner A, one with prunner B and three components
   running zero-prunner, annotated hence as Z|', Z|'' and Z|'''.  CDS
   within components are not visualized since they do not contribute to
   further understanding but the links that are included to connect the
   CDS of the component following Section 1.1.4 are made fat.  Obviously
   the overall graph is connected despite several algorithms and
   components the network encompasses on such, most likely not very
   likely, deployment.

Przygienda & Hegde        Expires 21 April 2025                 [Page 5]
Internet-Draft  Flooding Reduction Algorithm Interoperab    October 2024

   Figure 1 also visualizes why the overall CDS can be easily more than
   a spanning tree of the overall network.  A node seeing locally its
   neighbor running another algorithm cannot decide easily based simply
   on local knowledge whether the link should be included in flooding
   but could do so based on the overall view of the network of course
   and by some tie-breaking an algorithm to prune overall coverage to a
   spanning tree could be devised.  Due to possible resulting long
   flooding paths and one link minimal cuts such an algorithm is not
   considered here.  Of course in the future such an algorithm can be
   proposed with the nodes advertising whether they run such a 'prunner-
   of-prunners' while the absence of prunning can be denoted as 'zero-
   meta-prunner' to extend the symmetry of this solution recursively.

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

3.  Contributors

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

4.  Normative References

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

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

Przygienda & Hegde        Expires 21 April 2025                 [Page 6]
Internet-Draft  Flooding Reduction Algorithm Interoperab    October 2024

   [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 21 April 2025                 [Page 7]