Routing Area Working Group
Internet Engineering Task Force (IETF)                      S. Litkowski
Internet-Draft
Request for Comments: 8541                       Orange Business Service
Intended status:
Category: Informational                                      B. Decraene
Expires: July 20, 2019
ISSN: 2070-1721                                                   Orange
                                                            M. Horneffer
                                                        Deutsche Telekom
                                                        January 16,
                                                           February 2019

   Link State protocols SPF trigger

Impact of Shortest Path First (SPF) Trigger and delay algorithm impact Delay Strategies on IGP
                              micro-loops
               draft-ietf-rtgwg-spf-uloop-pb-statement-10
                              Micro-loops

Abstract

   A micro-loop is a packet forwarding packet-forwarding loop that may occur transiently
   among two or more routers in a hop-by-hop packet forwarding packet-forwarding paradigm.

   In this document, we are trying to analyze

   This document analyzes the impact of using different Link State link state IGP (Interior Gateway Protocol)
   implementations in a single network, network with respect to micro-loops.  The
   analysis is focused on the SPF (Shortest Shortest Path First) First (SPF) delay algorithm.

Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in BCP
   14 [RFC2119] [RFC8174] when, and only when, they appear in all
   capitals, as shown here. algorithm
   but also mentions the impact of SPF trigger strategies.

Status of This Memo

   This Internet-Draft document is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents not an Internet Standards Track specification; it is
   published for informational purposes.

   This document is a product of the Internet Engineering Task Force
   (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list  It represents the consensus of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft the IETF community.  It has
   received public review and has been approved for publication by the
   Internet Engineering Steering Group (IESG).  Not all documents valid
   approved by the IESG are candidates for a maximum any level of Internet
   Standard; see Section 2 of RFC 7841.

   Information about the current status of six months this document, any errata,
   and how to provide feedback on it may be updated, replaced, or obsoleted by other documents obtained 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 July 20, 2019.
   https://www.rfc-editor.org/info/rfc8541.

Copyright Notice

   Copyright (c) 2019 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 Statement . . . . . . . . . . . . . . . . . . . . . .   4   3
   3.  SPF trigger strategies Trigger Strategies  . . . . . . . . . . . . . . . . . . .   5
   4.  SPF delay strategies Delay Strategies  . . . . . . . . . . . . . . . . . . . .   6   5
     4.1.  Two steps  Two-Step SPF delay Delay  . . . . . . . . . . . . . . . . . . .   6
     4.2.  Exponential backoff . . . . Back-Off Delay  . . . . . . . . . . . . . . .   7   6
   5.  Mixing strategies Strategies . . . . . . . . . . . . . . . . . . . . . .   8
   6.  Benefits of standardized Standardized SPF delay behavior Delay Behavior . . . . . . . . .  12  11
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  13
   8.  Acknowledgements  .  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  13
   9.  IANA Considerations  References  . . . . . . . . . . . . . . . . . . . . . . . . .  13
   10.
     9.1.  Normative References  . . . . . . . . . . . . . . . . . .  13
     9.2.  Informative References  . . . . . . .  14
     10.1.  Normative References . . . . . . . . . . .  13
   Acknowledgements  . . . . . . .  14
     10.2.  Informative References . . . . . . . . . . . . . . . . .  14
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  15  14

1.  Introduction

   Link State state IGP protocols are based on a topology database on which
   the SPF algorithm is run to find a consistent set of non-looping
   routing paths.

   Specifications like IS-IS ([RFC1195]) [RFC1195] propose some optimizations of the
   route computation (See (see Appendix C.1 of [RFC1195]) [RFC1195]), but not all the
   implementations follow those non-mandatory optimizations.

   We will call "SPF triggers",

   In this document, we refer to the events that would lead to a new SPF
   computation based on the topology. topology as "SPF triggers".

   Link State state IGP protocols, like OSPF ([RFC2328]) [RFC2328] and IS-IS
   ([RFC1195]), are using [RFC1195],
   use multiple timers to control the router behavior in case of churn:
   SPF delay, PRC (Partial Partial Route Computation) Computation (PRC) delay,
   LSP (Link Link State Packet) Packet
   (LSP) generation delay, LSP flooding delay, and LSP retransmission interval...
   interval.

   Some of those timers (values the values and behavior) behaviors of these timers are standardized in
   protocol specifications, while and some are not.  The SPF computation computation-
   related timers have generally remained unspecified.

   For non standardized timers, implementations

   Implementations are free to implement
   them non-standardized timers in any
   way.  For some standardized timers, we can also see that
   rather than using static configurable values for such timer, implementations may offer
   dynamically adjusted timers to help control the churn.

   We will call churn rather than use
   static configurable values.

   "SPF delay", delay" refers to the timer that exists in most implementations that
   specifies the required delay before running an SPF computation after a
   an SPF trigger is received.

   A micro-loop is a packet forwarding packet-forwarding loop that may occur transiently
   among two or more routers in a hop-by-hop packet forwarding packet-forwarding paradigm.
   We can observe that these
   These micro-loops are formed when two routers do not update their
   Forwarding Information Base (FIB) Bases (FIBs) for a certain prefix at the same
   time.  The micro-loop phenomenon is described in
   [I-D.ietf-rtgwg-microloop-analysis]. [MICROLOOP-LSRP].

   Two micro-loop mitigation techniques have been defined by IETF.  The
   mechanism in [RFC6976] has not been widely implemented, presumably
   due to the complexity of the technique.  The mechanism in [RFC8333]
   has been implemented.  However, it does not prevent all micro-loops
   that can occur for a given topology and failure scenario.

   In multi-vendor networks, using different implementations of a link
   state protocol may favor micro-loops micro-loop creation during the convergence
   process due to discrepancies of in timers.  Service Providers are providers already aware
   know to use similar timers (values with similar values and behavior) behaviors for all of the
   network as a best practice, but sometimes it this is sometimes not possible due to
   the limitations of implementations.

   This document will present presents reasons for service providers to have
   consistent implementations implementation of Link State link state protocols across vendors.
   We are particularly analyzing  In
   particular, this document analyzes the impact of using different Link
   State link
   state IGP implementations in a single network in regards of with regard to micro-
   loops.  The analysis is focused focuses on the SPF delay algorithm.

   [RFC8405] defines a solution that partially addresses this problem
   statement
   statement, and this document captures the reasoning of the provided
   solution.

2.  Problem statement Statement

                              S ---- E
                              |      |
                           10 |      | 10
                              |      |
                              D ---- A
                              |  2
                              Px

            Figure 1 - 1: Network topology suffering from micro-loops Topology Experiencing Micro-loops
   Figure 1 represents a small network composed of four routers (S,D,E (S, D,
   E, and A).Router A).  Router S uses primarily uses the SD link to reach the prefixes
   behind router D (named Px).  When the SD link fails, the IGP
   convergence occurs.  If S converges before E, S will forward the
   traffic to Px through E, but as E; however, because E has not converged yet, E
   will loop
   back the traffic back to S, leading to a micro-loop.

   The micro-loop appears due to the asynchronous convergence of nodes
   in a network when an event occurs.

   Multiple factors (or a combination of these factors) may increase the
   probability for of a micro-loop to appear: appearing:

   o  the delay  Delay of failure notification: the The greater the time gap between E
      and S being advised of the failure, the more greater the chance that a micro-
      loop
      micro-loop may have a chance to appear.

   o  the  SPF delay: most Most implementations support a delay for the SPF
      computation to try to catch as many events as possible.  If S uses an SPF
      delay timer of x msec and ms, E uses an SPF delay timer of y
      msec ms, and x < y,
      E would start converging after S S, leading to a potential micro-loop. micro-
      loop.

   o  the  SPF computation time: This is mostly a matter of CPU power and
      optimizations like incremental SPF.  If S computes its SPF faster
      than E, there is a chance for a micro-loop to appear.  Today, CPUs
      are
      today fast enough to consider the SPF computation time as negligible
      (on the order of milliseconds in a large network).

   o  the  SPF computation ordering: an An SPF trigger can be common to multiple
      IGP areas or levels (e.g., IS-IS Level1/Level2) Level 1 and Level 2) or for to
      multiple address families with multi-topologies.  There is no
      specified order for SPF computation today today, and it is
      implementation dependent.  In such scenarios, if the order of SPF
      computation done in S and E for each area/level/topology/SPF-algorithm area, level, topology, or SPF
      algorithm is different, there is a possibility for a micro-loop to
      appear.

   o  the  RIB and FIB prefix insertion speed or ordering. ordering: This is highly
      dependent on the implementation.

   Even if all of these factors may increase the probability for of a micro-loop to appear,
   appearing, the SPF delay, delay plays a significant role, especially in case
   of churn,
   plays a significant role. churn.  As the number of IGP events increase, increases, the delta between
   the SPF delay values used by routers becomes significant
   and significant; in fact, it
   becomes the dominating factor (especially when one router increases
   its timer exponentially while another one increases it in a more smoother
   way).  Another important factor is the time to update the FIB.  As of
   today, the total FIB update time is the major factor for IGP
   convergence.  However, for micro-loops, what matters is not the total time,
   time but the difference to install in installing the same prefix between nodes.
   The time to update the FIB may be the main part for the first
   iteration but is not for subsequent IGP events.  In addition, the time
   to update the FIB is very implementation specific and difficult/impossible difficult or
   impossible to standardize, while the SPF delay algorithm may be
   standardized.

   As a consequence, this document will focus on the an analysis of the SPF
   delay behavior and associated triggers.

3.  SPF trigger strategies Trigger Strategies

   Depending on the change advertised in LSPDU (Link State Protocol Data
   Unit) the LSP or LSA (Link State
   Advertisement), the topology may be affected or not. may not be affected.  An
   implementation may avoid running the SPF computation (and may only
   run an IP reachability computation instead) if the advertised change
   does not affect the topology.

   Different strategies exists to can trigger the SPF computation:

   1.  An implementation may always run a full SPF for any type of
       change.

   2.  An implementation may run a full SPF only when required.  For
       example, if a link fails, a local node will run an SPF for its
       local LSP update.  If the LSP from the neighbor (describing the
       same failure) is received after SPF has started, the local node
       can decide that a new full SPF is not required as the topology
       has not changed.

   3.  If the topology does not change, an implementation may only
       recompute the IP reachability.

   As noted in Section 1, SPF optimizations are not mandatory in
   specifications.  This has led to the implementation of different
   strategies.

4.  SPF delay strategies Delay Strategies

   Implementations of link state routing protocols use different
   strategies to delay the SPF computation.  The two most common SPF delay
   behaviors are the following:

   1.  Two phase  Two-step SPF delay. delay

   2.  Exponential backoff delay. back-off delay
   These behaviors will be are explained in the next following sections.

4.1.  Two steps  Two-Step SPF delay Delay

   The SPF delay is managed by four parameters:

   o  Rapid  rapid delay: the amount of time to wait before running SPF, SPF after
      the initial SPF trigger event.

   o  Rapid  rapid runs: the number of consecutive SPF runs that can use the
      rapid delay.  When the number is exceeded, the delay moves to the
      slow delay value.

   o  Slow  slow delay: the amount of time to wait before running an SPF.

   o  Wait  wait time: the amount of time to wait without receiving detecting SPF
      trigger events before going back to the rapid delay.

   Example: Rapid

   Figure 2 displays the evolution of the SPF delay timer (based on a
   two-step delay algorithm) upon the reception of multiple events.
   Figure 2 considers the following parameters for the algorithm: rapid
   delay (RD) = 50msec, Rapid 50 ms, rapid runs = 3, Slow slow delay (SD) =
   1sec, Wait 1 s, wait time
   = 2sec 2 s.

   SPF delay time
       ^
       |
       |
   SD- |             x xx x
       |
       |
       |
   RD- |   x  x   x                    x
       |
       +---------------------------------> Events
           |  |   |  | || |            |
                           < wait time >

                  Figure 2 - Two phase delay algorithm 2: Two-Step SPF Delay Algorithm

4.2.  Exponential backoff Back-Off Delay

   The algorithm has two modes: the fast mode and the backoff back-off mode.  In
   the fast
   mode, the SPF delay is usually delayed by a very small amount of time
   (fast reaction).  When an SPF computation has is run in
   the fast mode, the
   algorithm automatically moves to the backoff back-off mode (a single SPF run is
   authorized in the fast mode).  In the backoff back-off mode, the SPF delay is increasing increases
   exponentially at in each run.  When the network becomes stable, the
   algorithm moves back to the fast mode.  The SPF delay is managed by four
   parameters:

   o  First  first delay: amount of time to wait before running SPF.  This
      delay is used only when SPF is in fast mode.

   o  Incremental  incremental delay: amount of time to wait before running SPF.
      This delay is used only when SPF is in backoff back-off mode and
      increments exponentially at each SPF run.

   o  Maximum  maximum delay: maximum amount of time to wait before running SPF.

   o  Wait  wait time: amount of time to wait without events before going back
      to the fast mode.

   Example: First

   Figure 3 displays the evolution of the SPF delay timer (based on an
   exponential back-off delay algorithm) upon the reception of multiple
   events.  Figure 3 considers the following parameters for the
   algorithm: first delay (FD) = 50msec, Incremental 50 ms, incremental delay (ID) = 50msec,
   Maximum 50 ms,
   maximum delay (MD) = 1sec, Wait 1 s, wait time = 2sec 2 s

   SPF delay time
       ^
   MD- |               xx x
       |
       |
       |
       |
       |
       |             x
       |
       |
       |
       |          x
       |
   FD- |   x  x                        x
   ID  |
       +---------------------------------> Events
           |  |   |  | || |            |
                           < wait time >
          FM->BM -------------------->FM

              Figure 3 - 3: Exponential delay algorithm Back-Off Delay Algorithm

5.  Mixing strategies

   In Strategies

   Figure 1, we consider 1 illustrates a flow of packet packets from S to D.  We consider
   that  S is using uses optimized
   SPF triggering (Full (full SPF is triggered only when necessary), necessary) and two steps two-
   step SPF delay (rapid=150ms,rapid-runs=3,
   slow=1s). (rapid delay = 150 ms, rapid runs = 3, slow delay = 1
   s).  As the implementation of S is optimized, Partial Reachability
   Computation (PRC) PRC is available.  We  For
   PRC delay, we consider the same timers as SPF for delaying PRC.  We consider that SPF delay.  E is using a uses an
   SPF trigger strategy that always compute computes a Full full SPF for any change, change
   and uses the exponential backoff back-off strategy for SPF delay (start=150ms, inc=150ms,
   max=1s)

   We also consider (first delay
   = 150 ms, incremental delay = 150 ms, maximum delay = 1 s).

   Consider the following sequence of events:

   o  t0=0 ms: a A prefix is declared down in the network.  We consider
      this  This event to happen
      happens at time=0.

   o  200ms: the  200 ms: The prefix is declared as up.

   o  400ms: a  400 ms: The prefix is declared down in the network.

   o  1000ms:  1000 ms: S-D link fails.

   +--------+--------------------+------------------+------------------+

   +---------+-------------------+------------------+------------------+
   |   Time  |   Network Event   | Router S events Events  | Router E events Events  |
   +--------+--------------------+------------------+------------------+
   +---------+-------------------+------------------+------------------+
   |   t0=0  |    Prefix DOWN    |                  |                  |
   |  10ms  10 ms  |                   | Schedule PRC (in | Schedule SPF (in |
   |         |                   |      150ms)     150 ms)      |      150ms)     150 ms)      |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 160ms  160 ms |                   |    PRC starts    |    SPF starts    |
   | 161ms  161 ms |                   |     PRC ends     |                  |
   | 162ms  162 ms |                   |  RIB/FIB starts  |                  |
   | 163ms  163 ms |                   |                  |     SPF ends     |
   | 164ms  164 ms |                   |                  |  RIB/FIB starts  |
   | 175ms  175 ms |                   |   RIB/FIB ends   |                  |
   | 178ms  178 ms |                   |                  |   RIB/FIB ends   |
   |         |                   |                  |                  |
   | 200ms  200 ms |     Prefix UP     |                  |                  |
   | 212ms  212 ms |                   | Schedule PRC (in |                  |
   |         |                   |      150ms)     150 ms)      |                  |
   | 214ms  214 ms |                   |                  | Schedule SPF (in |
   |         |                   |                  |      150ms)     150 ms)      |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 370ms  370 ms |                   |    PRC starts    |                  |
   | 372ms  372 ms |                   |     PRC ends     |                  |
   | 373ms  373 ms |                   |                  |    SPF starts    |
   | 373ms  373 ms |                   |  RIB/FIB starts  |                  |
   | 375ms  375 ms |                   |                  |     SPF ends     |
   | 376ms  376 ms |                   |                  |  RIB/FIB starts  |
   | 383ms  383 ms |                   |   RIB/FIB ends   |                  |
   | 385ms  385 ms |                   |                  |   RIB/FIB ends   |
   |         |                   |                  |                  |
   | 400ms  400 ms |    Prefix DOWN    |                  |                  |
   | 410ms  410 ms |                   | Schedule PRC (in | Schedule SPF (in |
   |         |                   |      300ms)     300 ms)      |      300ms)     300 ms)      |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 710ms  710 ms |                   |    PRC starts    |    SPF starts    |
   | 711ms  711 ms |                   |     PRC ends     |                  |
   | 712ms  712 ms |                   |  RIB/FIB starts  |                  |
   | 713ms  713 ms |                   |                  |     SPF ends     |
   | 714ms  714 ms |                   |                  |  RIB/FIB starts  |
   | 716ms  716 ms |                   |   RIB/FIB ends   |   RIB/FIB ends   |
   |         |                   |                  |                  |
   | 1000ms 1000 ms |   S-D link DOWN   |                  |                  |
   | 1010ms 1010 ms |                   | Schedule SPF (in | Schedule SPF (in |
   |         |                   |      150ms)     150 ms)      |      600ms)     600 ms)      |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 1160ms 1160 ms |                   |    SPF starts    |                  |
   | 1161ms 1161 ms |                   |     SPF ends     |                  |
   | 1162ms 1162 ms |   Micro-loop may  |  RIB/FIB starts  |                  |
   |         |  start from here  |                  |                  |
   | 1175ms 1175 ms |                   |   RIB/FIB ends   |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 1612ms 1612 ms |                   |                  |    SPF starts    |
   | 1615ms 1615 ms |                   |                  |     SPF ends     |
   | 1616ms 1616 ms |                   |                  |  RIB/FIB starts  |
   | 1626ms 1626 ms |  Micro-loop ends  |                  |   RIB/FIB ends   |
   +--------+--------------------+------------------+------------------+
   +---------+-------------------+------------------+------------------+

    Table 1 - 1: Route computation when Computation When S and E use the different behaviors Use Different Behaviors and multiple events appear
                          Multiple Events Appear

   In the Table 1, we can see that due to discrepancies in the SPF
   management, management and after
   multiple events of a different type, types, the values of the SPF delay are
   completely misaligned between node S and node E, leading to the
   creation of micro-loops.

   The same issue can also appear with only a single type of event as
   shown below:

   +--------+--------------------+------------------+------------------+

   +---------+-------------------+------------------+------------------+
   |   Time  |   Network Event   | Router S events Events  | Router E events Events  |
   +--------+--------------------+------------------+------------------+
   +---------+-------------------+------------------+------------------+
   |   t0=0  |     Link DOWN     |                  |                  |
   |  10ms  10 ms  |                   | Schedule SPF (in | Schedule SPF (in |
   |         |                   |      150ms)     150 ms)      |      150ms)     150 ms)      |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 160ms  160 ms |                   |    SPF starts    |    SPF starts    |
   | 161ms  161 ms |                   |     SPF ends     |                  |
   | 162ms  162 ms |                   |  RIB/FIB starts  |                  |
   | 163ms  163 ms |                   |                  |     SPF ends     |
   | 164ms  164 ms |                   |                  |  RIB/FIB starts  |
   | 175ms  175 ms |                   |   RIB/FIB ends   |                  |
   | 178ms  178 ms |                   |                  |   RIB/FIB ends   |
   |         |                   |                  |                  |
   | 200ms  200 ms |     Link DOWN     |                  |                  |
   | 212ms  212 ms |                   | Schedule SPF (in |                  |
   |         |                   |      150ms)     150 ms)      |                  |
   | 214ms  214 ms |                   |                  | Schedule SPF (in |
   |         |                   |                  |      150ms)     150 ms)      |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 370ms  370 ms |                   |    SPF starts    |                  |
   | 372ms  372 ms |                   |     SPF ends     |                  |
   | 373ms  373 ms |                   |                  |    SPF starts    |
   | 373ms  373 ms |                   |  RIB/FIB starts  |                  |
   | 375ms  375 ms |                   |                  |     SPF ends     |
   | 376ms  376 ms |                   |                  |  RIB/FIB starts  |
   | 383ms  383 ms |                   |   RIB/FIB ends   |                  |
   | 385ms  385 ms |                   |                  |   RIB/FIB ends   |
   |         |                   |                  |                  |
   | 400ms  400 ms |     Link DOWN     |                  |                  |
   | 410ms  410 ms |                   | Schedule SPF (in | Schedule SPF (in |
   |         |                   |      150ms)     150 ms)      |      300ms)     300 ms)      |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 560ms  560 ms |                   |    SPF starts    |                  |
   | 561ms  561 ms |                   |     SPF ends     |                  |
   | 562ms  562 ms |   Micro-loop may  |  RIB/FIB starts  |                  |
   |         |  start from here  |                  |                  |
   | 568ms  568 ms |                   |   RIB/FIB ends   |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 710ms  710 ms |                   |                  |    SPF starts    |
   | 713ms  713 ms |                   |                  |     SPF ends     |
   | 714ms  714 ms |                   |                  |  RIB/FIB starts  |
   | 716ms  716 ms |  Micro-loop ends  |                  |   RIB/FIB ends   |
   |         |                   |                  |                  |
   | 1000ms 1000 ms |     Link DOWN     |                  |                  |
   | 1010ms 1010 ms |                   | Schedule SPF (in | Schedule SPF (in |
   |         |                   |       1s)       1 s)       |      600ms)     600 ms)      |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 1612ms 1612 ms |                   |                  |    SPF starts    |
   | 1615ms 1615 ms |                   |                  |     SPF ends     |
   | 1616ms 1616 ms |   Micro-loop may  |                  |  RIB/FIB starts  |
   |         |  start from here  |                  |                  |
   | 1626ms 1626 ms |                   |                  |   RIB/FIB ends   |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 2012ms 2012 ms |                   |    SPF starts    |                  |
   | 2014ms 2014 ms |                   |     SPF ends     |                  |
   | 2015ms 2015 ms |                   |  RIB/FIB starts  |                  |
   | 2025ms 2025 ms |  Micro-loop ends  |   RIB/FIB ends   |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   +--------+--------------------+------------------+------------------+
   +---------+-------------------+------------------+------------------+

   Table 2 - 2: Route computation Computation upon multiple link down events when Multiple Link Down Events When S and
                         E use the different behaviors Use Different Behaviors

6.  Benefits of standardized Standardized SPF delay behavior

   Using Delay Behavior

   Table 3 uses the same event sequence as in Table 1, we may expect fewer and/
   or 1.  Fewer and/or
   shorter micro-loops are expected using a standardized SPF delay.

   +--------+--------------------+------------------+------------------+

   +---------+-------------------+------------------+------------------+
   |   Time  |   Network Event   | Router S events Events  | Router E events Events  |
   +--------+--------------------+------------------+------------------+
   +---------+-------------------+------------------+------------------+
   |   t0=0  |    Prefix DOWN    |                  |                  |
   |  10ms  10 ms  |                   | Schedule PRC (in | Schedule PRC (in |
   |         |                   |      150ms)     150 ms)      |      150ms)     150 ms)      |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 160ms  160 ms |                   |    PRC starts    |    PRC starts    |
   | 161ms  161 ms |                   |     PRC ends     |                  |
   | 162ms  162 ms |                   |  RIB/FIB starts  |     PRC ends     |
   | 163ms  163 ms |                   |                  |  RIB/FIB starts  |
   | 175ms  175 ms |                   |   RIB/FIB ends   |                  |
   | 176ms  176 ms |                   |                  |   RIB/FIB ends   |
   |         |                   |                  |                  |
   | 200ms  200 ms |     Prefix UP     |                  |                  |
   | 212ms  212 ms |                   | Schedule PRC (in |                  |
   |         |                   |      150ms)     150 ms)      |                  |
   | 213ms  213 ms |                   |                  | Schedule PRC (in |
   |         |                   |                  |      150ms)     150 ms)      |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 370ms  370 ms |                   |    PRC starts    |    PRC starts    |
   | 372ms  372 ms |                   |     PRC ends     |                  |
   | 373ms  373 ms |                   |  RIB/FIB starts  |     PRC ends     |
   | 374ms  374 ms |                   |                  |  RIB/FIB starts  |
   | 383ms  383 ms |                   |   RIB/FIB ends   |                  |
   | 384ms  384 ms |                   |                  |   RIB/FIB ends   |
   |         |                   |                  |                  |
   | 400ms  400 ms |    Prefix DOWN    |                  |                  |
   | 410ms  410 ms |                   | Schedule PRC (in | Schedule PRC (in |
   |         |                   |      300ms)     300 ms)      |      300ms)     300 ms)      |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 710ms  710 ms |                   |    PRC starts    |    PRC starts    |
   | 711ms  711 ms |                   |     PRC ends     |     PRC ends     |
   | 712ms  712 ms |                   |  RIB/FIB starts  |                  |
   | 713ms  713 ms |                   |                  |  RIB/FIB starts  |
   | 716ms  716 ms |                   |   RIB/FIB ends   |   RIB/FIB ends   |
   |         |                   |                  |                  |
   | 1000ms 1000 ms |   S-D link DOWN   |                  |                  |
   | 1010ms 1010 ms |                   | Schedule SPF (in | Schedule SPF (in |
   |         |                   |      150ms)     150 ms)      |      150ms)     150 ms)      |
   |         |                   |                  |                  |
   |         |                   |                  |                  |
   | 1160ms 1160 ms |                   |    SPF starts    |                  |
   | 1161ms 1161 ms |                   |     SPF ends     |    SPF starts    |
   | 1162ms 1162 ms |   Micro-loop may  |  RIB/FIB starts  |     SPF ends     |
   |         |  start from here  |                  |                  |
   | 1163ms 1163 ms |                   |                  |  RIB/FIB starts  |
   | 1175ms 1175 ms |                   |   RIB/FIB ends   |                  |
   | 1177ms 1177 ms |  Micro-loop ends  |                  |   RIB/FIB ends   |
   +--------+--------------------+------------------+------------------+
   +---------+-------------------+------------------+------------------+

     Table 3 - 3: Route computation when Computation When S and E use Use the same standardized
                                 behavior Same Standardized
                                 Behavior
   As displayed above, there could can be some other parameters parameters, like router
   computation power, power and flooding timers timers, that may also influence micro-
   loops.  In all the examples in this document comparing the SPF timer
   behavior of router S and router E, we have made router E a bit slower
   than router S.  This can lead to micro-loops even when both S and E
   use a common standardized SPF behavior.  However, we expect that by aligning
   implementations of the SPF delay, we expect that service providers
   may reduce the number and the duration of micro-loops.

7.  Security Considerations

   This document does not introduce any security consideration. considerations.

8.  Acknowledgements

   Authors would like to thank Mike Shand and Chris Bowers for their
   useful comments.

9.  IANA Considerations

   This document has no action actions for IANA.

10.

9.  References

10.1.

9.1.  Normative References

   [RFC1195]  Callon, R., "Use of OSI IS-IS for routing in TCP/IP and
              dual environments", RFC 1195, DOI 10.17487/RFC1195,
              December 1990, <https://www.rfc-editor.org/info/rfc1195>.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/info/rfc2119>.

   [RFC2328]  Moy, J., "OSPF Version 2", STD 54, RFC 2328,
              DOI 10.17487/RFC2328, April 1998,
              <https://www.rfc-editor.org/info/rfc2328>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/info/rfc8174>.

   [RFC8405]  Decraene, B., Litkowski, S., Gredler, H., Lindem, A.,
              Francois, P., and C. Bowers, "Shortest Path First (SPF)
              Back-Off Delay Algorithm for Link-State IGPs", RFC 8405,
              DOI 10.17487/RFC8405, June 2018,
              <https://www.rfc-editor.org/info/rfc8405>.

10.2.

9.2.  Informative References

   [I-D.ietf-rtgwg-microloop-analysis]

   [MICROLOOP-LSRP]
              Zinin, A., "Analysis and Minimization of Microloops in
              Link-state Routing Protocols", draft-ietf-rtgwg-microloop-
              analysis-01 (work Work in progress), Progress, draft-
              ietf-rtgwg-microloop-analysis-01, October 2005.

   [RFC6976]  Shand, M., Bryant, S., Previdi, S., Filsfils, C.,
              Francois, P., and O. Bonaventure, "Framework for Loop-Free
              Convergence Using the Ordered Forwarding Information Base
              (oFIB) Approach", RFC 6976, DOI 10.17487/RFC6976, July
              2013, <https://www.rfc-editor.org/info/rfc6976>.

   [RFC8333]  Litkowski, S., Decraene, B., Filsfils, C., and P.
              Francois, "Micro-loop Prevention by Introducing a Local
              Convergence Delay", RFC 8333, DOI 10.17487/RFC8333, March
              2018, <https://www.rfc-editor.org/info/rfc8333>.

Acknowledgements

   The authors would like to thank Mike Shand and Chris Bowers for their
   useful comments.

Authors' Addresses

   Stephane Litkowski
   Orange Business Service

   Email: stephane.litkowski@orange.com

   Bruno Decraene
   Orange

   Email: bruno.decraene@orange.com

   Martin Horneffer
   Deutsche Telekom

   Email: martin.horneffer@telekom.de