Network Working Group                                         Alex Zinin
Internet Draft                                                   Alcatel
Expiration Date: April 2005                                 October 2004
File name: draft-zinin-microloop-analysis-00.txt


               Analysis and Minimization of Microloops in
                      Link-state Routing Protocols

                 draft-zinin-microloop-analysis-00.txt




Status of this Memo

   This document is an Internet-Draft and is subject to all provisions
   of section 3 of RFC 3667.  By submitting this Internet-Draft, each
   author represents that any applicable patent or other IPR claims of
   which he or she is aware have been or will be disclosed, and any of
   which he or she become aware will be disclosed, in accordance with
   RFC 3668.

   Internet Drafts are working documents of the Internet Engineering
   Task Force (IETF), its Areas, and its Working Groups. Note that other
   groups may also distribute working documents as Internet Drafts.

   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 a "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.


Abstract

   Link-state routing protocols (e.g. OSPF or IS-IS) are known to
   converge to a loop-free state within a finite period of time after a
   failure. It is normal, however, to observe short-term loops during
   the period of failure propagation, route recalculation, and
   forwarding table update, due to the asynchronous nature of link-state
   protocol operation. This document provides an analysis of formation
   of such microloops and suggests simple mechanisms to minimize them.



Zinin                                                           [Page 1]


INTERNET DRAFT    IGP Microloop Analysis & Minimization     October 2004


1 Introduction

   Link-state routing protocols, such as [OSPF] and [ISIS] converge to a
   loop-free state within a finite period of time after a failure.
   Additional failures postpone the convergence, but do not get in its
   way.

   During the period of convergence, however, link-state protocols
   exhibit short-term routing table inconsistencies caused by the
   protocol's asynchronous nature.  These incornsistencies may cause
   short-term packet loops, also known as microloops. For example, see a
   sample network in Figure 1.

                         +--+    1    +--+
                         |A |---------|B |
                         +--+         +--+
                          |  \  10      |
                         5|   ------    |1
                          |         \   |
                         +--+   10   \+--+
                         |E |---------|C |
                         +--+         +--+
                             \_      /
                            5  \    /1 (failure)
                                +--+
                                |D |
                                +--+

                        Figure 1. Microloop example

   We are interested in routers A and B and their best paths towards D.
   Before failure, B's best path to D is B-C-D with cost 2, and A's best
   path is A-B-C-D with cost 3.  When link C-D fails, both C and D
   announce their link state information with link C-D missing. Within
   finite period of time, both A and B shall receive the topology update
   and converge on it, installing new best paths: A-E-D (10) for A, and
   B-A-E-D (11) for B.  However, if, due to timing differences, B
   calculates and installs its new best path through A before A has a
   chance to switch from B to E, a microloop will form between A and B
   for the duration of time required for A to complete its routing table
   update.

   Similar microloops may form when other topological changes happen in
   the network.  For example, a new link or a node is added, a link cost
   is changed, etc. In summary, whenever a topological change in the
   network results in changes of the shortest path three (SPT) for more
   than one node, it is possible for the network to exhibit temporary
   loops.



Zinin                                                           [Page 2]


INTERNET DRAFT    IGP Microloop Analysis & Minimization     October 2004


   This document provides an analysis of microloop formation.
   Specifically, we categorize different types of reconvergence
   scenarios, and explore their properties. We then show that in certain
   scenaiors microloops do not form, in others they can be eliminated
   using simple techniques described in this document, and define
   scenarios where more sophisticated loop avoidance mechanisms may be
   necessary.

2 Analysis

   To analyse the behavior of a network during reconvergence, we look at
   a given router and its neighbors before failure and during the
   transition to the new routes. More specifically, we analyse whether
   switching to the new routing information can result in loop formation
   or not.

2.1 Terminology

   The following terms are used in the draft.

     Downstream neighbor
          Neighbor N of router S is considered S's downstream neighbor
          for destination D, if Dopt(N, D) < Dopt(S, D)

     Primary neighbor
          Neighbor N of router S is considered S's primary neighbor for
          destination D, if N provides the shortest path to D according
          to the SPF calculation.

     Loop-free neighbor
          Neighbor N of router S is considered S's loop-free neighbor
          for destination D, if Dopt(N, D) < Dopt(N, S) + Dopt(S, D).
          Note that a loop-free neighbor may be, for example, router's
          primary before or after failure.

 2.2 Next hop safety condition

   We start the analysis with the following observation:

     When router X learns about a topology change and starts using
     neighbor Y as its new primary neighbor for a given destination, a
     microloop between X and Y can only form if the topology before
     failure of topology after failure are such that Y uses X as its
     primary neighbor for the same destination.

     Indeed, if the topologies before and after failure are such that Y
     does not use X as it's next hop, then there is no moment in time
     before Y learned about the failure or after it learned about it



Zinin                                                           [Page 3]


INTERNET DRAFT    IGP Microloop Analysis & Minimization     October 2004


     when it would forward traffic to X. Hence, at least one of the two
     topologies must be such that Y uses X as its next hop for a
     microloop between X and Y to form.

   Based on the above, we can define a safety condition for neighbor Y
   of router X that has just learned about a topology change. Note that
   the condition must satisfy the topological criteria above, and be
   non-recursive, i.e. not lead to loops if both X and Y follow it.

     Next-hop safety condition:

          After a topology change, it is safe for router X to switch to
          neigbor Y as its next-hop for a specific destination if the
          path through Y satisfies both of the following criteria:

          1.   X considered Y as its loop-free neighbor based on the
               topology before change AND

          2:   X considers Y as its downstream neighbor based on the
               topology after change.

          The first requirement ensures that Y has not been forwarding
          traffic to X before the change occured and both X and Y used
          old topology. The second requirement makes sure Y does not
          forward traffic to X when Y learns the new topology.

          The difference in the two characteristics is there to make
          sure that X and Y do not recursively consider each other as
          safe next-hops when they learn about the failure.

 3.2 Transition types

   Here, we analyse different types of scenarios that a given router may
   find itself in after learning about a topology change.

   For each topological change, the network will have three major types
   of nodes categorized by the degree of safety of their old primary,
   new primary, and other neighbors.


     Type A

          Routers whose new primary next-hops after the topology change
          are safe and transition to them will not create a microloop.
          Two subtypes are recognized:

          A1:  Routers whose SPT hasn't been affected by the topology
               change, and hence their primaries haven't changed.



Zinin                                                           [Page 4]


INTERNET DRAFT    IGP Microloop Analysis & Minimization     October 2004


          A2:  Routers whose new primary satisfies the safety condition


     Type B

          Routers whose new primary next-hops after the topology change
          do not satisfy the safety condition, but that have at least
          one other neighbor that does. Note that such a neighbor can be
          the router's old primary (type B1) or a neighbor that is nei-
          ther old nor new primary (type B2).


     Type C

          Routers that have no neighbor that satisfies the safety condi-
          tion.

   It is clear that type-A routers can immediately switch to their new
   primary next hops once they are calculated after the topology change.

   It can also be shown that if type-B routers do not immediately switch
   to their new primaries, but use their safe next-hops for some time,
   switching to the new primaries later will not create loops, provided
   that their downstream routers have also switched to the safe hops or
   have already switched to the new primaries.

   The following section defines this mechanism more formally.

3.3 Basic loop prevention mechanism

   On discovering the topology change and calculating the new SPT, each
   router checks the safety status of each neighbor using the condition
   in section 3.1, calculates the new routes, and applies the following
   logic for each route depending on the type of role it finds itself
   in:


     Type A:
          The new route can be installed immediately.

     Type B:
          The new route is installed with one or more temporary next-
          hops that satisfy the safety condition. The router uses these
          safe next-hops for time DELAY_TYPEB, and only then installs
          the new primary next-hops.

     Type C:
          Installation of the new route is delayed by time DELAY_TYPEC.



Zinin                                                           [Page 5]


INTERNET DRAFT    IGP Microloop Analysis & Minimization     October 2004


          Until then, the router continues to use its old next-hops.

   DELAY_TYPEB and DELAY_TYPEC are two configurable constants. They
   should be configured with the same value on all routers in the net-
   work and such that following equation is true:

      DELAY_TYPEB > DELAY_TYPEC > fault-propagation-time

   where fault-propagation-time is the time it is expected to take
   routers in the network to propagate new link-state information, cal-
   culate the new SPT, check the safety condition of the neighbors, and
   install required FIB entries.

   Suggested default values for DELAY_TYPEB and DELAY_TYPEC are 4 and 2
   seconds correspondingly.

   Note that if routers in the network already implement [IPFRR], this
   algorithm adds minimal complexity. Its other advantage is that it
   does not require explicit ordering or signaling between routers. Each
   router determines its type relative to the experienced failure and
   decides how to transition.

   The above algorithm minimizes the probability of loop formation. More
   specifically, loops will only be possible when two neighboring
   routers both experience the type C condition after the topology
   change. Appendix A shows that transitions between A-A, A-B, A-C, and
   B-C routers are loop-free.

2.6 Coverage analysis
     <tbd>

3 Security Considerations
     <tbd>


Appendix A. Loop formation analysis


   S is the calculating router discovering the failure through a link-
   state update. P is the old primary, NP is the new primary.

    BF:
                        <------
            [P]----------------[S]----------------[NP]
               ...>?

    AF:




Zinin                                                           [Page 6]


INTERNET DRAFT    IGP Microloop Analysis & Minimization     October 2004


                                  ------>
            [P]----------------[S]----------------[NP]
                                              ?<...

   To analyze possible loop formation, we need to check the following:


     1)   if it is possible for P to start forwarding packets to S
          before S switches to NP

     2)   if it is possible for NP to be forwarding packets back to S
          before or after S starts using it

   Assumptions are that type-As switch-over to NP immediately, and type-
   Bs and type-Cs wait certain amount of time so that:

      DELAY_TYPEB > DELAY_TYPEC > fault-propagation-time

   1. S is type A:

   BF analysis:

     1.1 If P is another type-A, then S cannot be its new primary, since
     S has not been P's LFA before (since it's been fwd'ing through P).
     Hence, P will not route through S AF, and the will be no loops
     between P and S.

     1.2 If P is a type-B, then S hasn't been P's LF neighbor BF, and P
     will not forward through S at least for DELAY_TYPEB, which gives S
     enough time to switch to NP. After DELAY_TYPEB P may start using S
     as it's new primary.

     1.3 If P is a type-C, then it hasn't been forwarding traffic to S
     BF, and will not use S as its new primary at least for DELAY_TYPEC,
     which should give S enough time to switch to NP.

     1.4 Consequently, no loops will form between a type-A node and it's
     old primary before the type-A nodes switches to its new primary.

   AF analysis:

     1.5 Regardless of its type, NP has not been forwarding packets to S
     BF and will not do so AF by definition of type-A.

     1.6 Consequently, no loops will form between a type-A node and it's
     new primary before or after the type-A nodes switches to it.

   2. S is type B:



Zinin                                                           [Page 7]


INTERNET DRAFT    IGP Microloop Analysis & Minimization     October 2004


   BF analysis:

     2.1 If P is a type-A, then similarly to 1.1 above, there will be no
     routes between P and S.

     2.2 If P is another type-B, then similarly to 1.2, S will not be
     used by P for at least DELAY_TYPEB, and S will have enough time to
     switch to its safe hops or NP.

     2.3 If P is a type-C, then similarly to 1.3, S hasn't been receiv-
     ing traffic from P BF, and will not AF for at least DELAY_TYPEC,
     which should give S enough time to switch to its safe hops or NP.

     2.4 Consequently, no loops will form between a type-B node and it's
     old primary before the type-B nodes switches to its new primary.

   AF analysis:

     2.5 If NP is a type-A, then because of the DELAY_TYPEB NP must have
     had enough time to switch to its new NP, which cannot be S by defi-
     nition of SPT considering that NP is S's new nexthop in the SPT AF.

     2.6 If NP is another type-B, then because of DELAY_TYPEB, NP must
     have had enough time to switch from its old primary and can equally
     likely be routing through either its safe hops, or its new primary.
     Neither of the two can be S by definition of a downstream node (for
     safe hops) and SPT (for new primary).

     2.7 If NP is a type-C, then because DELAY_TYPEB > DELAY_TYPEC, NP
     must have had enough time to switch to its new primary, which can't
     be S by definition of SPT and considering that NP is S's nexthop in
     the SPT AF.

     2.8 Consequently, no loops will form between a type-B node and it's
     new primary before or after the type-A nodes switches to it.

   3. S is type C:

   BF analysis:

     3.1 If P is a type-A, then similarly to 1.1 before, S has not been
     P's LF neighbor before and hence won't be its new primary, so no
     loops will form between P and S.

     3.2 If P is a type-B, then similarly to 1.2, S will not be used by
     P for at least DELAY_TYPEB, and because DELAY_TYPEB > DELAY_TYPEC,
     S will have enough time to switch to NP.




Zinin                                                           [Page 8]


INTERNET DRAFT    IGP Microloop Analysis & Minimization     October 2004


     3.3 If P is another type-C, then it hasn't been using S as its pri-
     mary BF, but it is possible for P to consider S as its new primary
     AF and to install routes before S after their DELAY_TYPEC expires.
     Hence, a microloop is possible between P and S.

     3.4 Consequently, a microloop between a type-C node and its old
     primary is possible only if the old primary is also a type-C node
     and it considers S as its new primary AF. Note that DELAY_TYPEC
     only delays probably loop formation, but does not increase its
     duration, as both neighboring routers are using the same delay.

   AF analysis:

     3.5 If NP is a type-A, then because of the DELAY_TYPEC NP must have
     had enough time to switch to its new NP, which cannot be S by defi-
     nition of SPT considering that NP is S's new nexthop in the SPT AF.

     3.6 If NP is a type-B, then because of DELAY_TYPEC, NP must have
     had enough time to switch to its safe hops, which can't be S by
     definition of a downstream node and considering that NP is S's new
     SPT next-hop.

     3.7 If NP is another type-C, a loop is possible if S's DELAY_TYPEC
     expires before that on NP and NP has been using S as its primary
     BF.

     3.8 Consequently, a microloop between a type-C node and its new
     primary is possible only if the new primary is also a type-C node
     and S was NP's primary BF.

   4. Given the above analysis, it can be noted that, for a given fail-
   ure, presence of single type-C nodes in the network does not create
   microloops.
    It is the C-C combination that introduces this potential.


Acknowledgements

   The author would like to thank Don Fedyk, Chris Martin, Mike Shand,
   and Alex Audu, for the discussion on this idea. Special thanks go to
   Alia Atlas who, among other things, was instrumental in fine-tuning
   the safety condition.

References

   [Ref1] Ref1 full

Author's Address



Zinin                                                           [Page 9]


INTERNET DRAFT    IGP Microloop Analysis & Minimization     October 2004


    Alex Zinin
    Alcatel
    701 E Middlefield Rd
    Mountain View, CA 94043
    E-mail: zinin@psg.com

IPR Disclaimer

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed
   to pertain to the implementation or use of the technology
   described in this document or the extent to which any license
   under such rights might or might not be available; nor does it
   represent that it has made any independent effort to identify any
   such rights.  Information on the procedures with respect to rights
   in RFC documents can be found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use
   of such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository
   at http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention
   any copyrights, patents or patent applications, or other
   proprietary rights that may cover technology that may be required
   to implement this standard.  Please address the information to the
   IETF at ietf-ipr@ietf.org.

Full Copyright Statement

   Copyright (C) The Internet Society (2004). This document is subject
   to the rights, licenses and restrictions contained in BCP 78, and
   except as set forth therein, the authors retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
   INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
   INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.








Zinin                                                          [Page 10]